按C中元素出现频率的降序对数组进行排序 [英] Sort the array in decreasing order of frequency of occurrence of elements in C

问题描述

问题是根据元素的频率对数组进行排序.例如，如果输入数组是

Question is to sort the array according to the frequency of the elements. For example, if the input array is

   { 2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12 }

然后将数组修改为:

   { 3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5 }

我为此编写了代码，并且可以正常工作，但是它占用了大量空间，并且具有很高的复杂性.

I wrote the code for this and it is working correctly, but it is using a lot of space and has very high complexity.

我对这种解决方案以及为此申请的逻辑不满意.任何人都可以帮助优化此代码或提供更好的逻辑吗?

I am not satisfied with this solution and the logic I applied for this. Can anyone help to optimize this code or provide a better logic?

我的代码是:

#define _CRT_SECURE_NO_WARNINGS // this line to work code in visual studio
#include <stdio.h>

int main() {
    /*
     * n = number of integer
     * i = loop variable
     * j = inner loop variable
     * c = number of distinct input
     * buf = temprary storage for input value
     * k = possibility of frequency of any no.
     */

    int n, i, j, c = 0, buf, k;
    int b; //act as flag
    int arr[100] = { 0 };
    int stack[200] = { 0 };
    int top = -1;
    printf("Enter the size of array(integer between 1-100):");
    scanf("%d", &n);
    n *= 2;

    printf("----------Enter the elements in the array----------\n\n");

    for (i = 0; i < n; i += 2) {
        b = 0;
        printf("Enter the element:");
        scanf("%d", &buf);
        for (j = 0; j <= i; j += 2) {
            if (arr[j] == buf) {
                arr[j + 1]++;
                b = 1;
            }       
        }
        if (b == 0) {
            c++;
            arr[c * 2 - 2] = buf;
            arr[c * 2 - 1]++;
        }
    }

    for (i = 0; i < c * 2; i++)
        printf("%d ", arr[i]);

    //input done in form of (element,times of occurence i.e. frequency),to print array, write this outside of comment: 
    //for (i = 0; i < c * 2; i++) printf("%d ", arr[i]);

    for (k = 1; k < n / 2; k++) {   //checking for possible frequencies
        for (j = c * 2 - 1; j > 0; j -= 2) {
            //locations(index) to check in array for frequency
            //left to right, so with same frequency no.,which occurred first will push in last.
            if (arr[j] == k)
                stack[++top] = j; //pushing(index of frequency) into stack in increasing order of frequency     
        }
    }

    //to print stack, write this outside of comment:
    //printf("\nstack\n");
    //for (i = top; i > -1; i--) printf("%d ",stack[i]);

    //printing of elements in there decreasing order of frequency(pop from stack)
    //we have to print element, number of times of its frequency

    printf("\n\n----------Output array in sorted order of there frequency----------\n");
    for (top; top > -1; top--) {        
        for (j = arr[stack[top]]; j > 0; j--)
            printf("%d ", arr[stack[top] - 1]);
    }
}

推荐答案

按值对数组进行排序；RLE结果，将等于的每个跨度转换为一对元素和跨度的长度(您可以使用辅助数组来支持第二个分量)；对第二对组件按降序排序；有你的结果.全部用 O(n log n)时间和 O(n)附加空间.

Sort the array by value; RLE the result, turning each span of equals into a pair of the element and the span's length (you can use an auxiliary array to back the second component); sort the pairs in descending order by the second component; there's your result. All in O(n log n) time and O(n) additional space.

这篇关于按C中元素出现频率的降序对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！