按C中元素出现频率的降序排列数组

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

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

然后将数组修改为：

{ 3,5 }

我为此编写了代码并且它正常工作,但它使用了大量空间并且具有非常高的复杂性.

我对这个解决方案和我申请的逻辑不满意.如果有人帮助优化此代码或提供更好的逻辑.

我的代码是：

#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]);
    }
}

解决方法

如果O(N2)和平均复杂度为O(N.log(N)),我已经找到了一种优雅的方法来执行这种排序,最坏情况复杂.

该方法使用以下步骤：

>通过增加值的顺序对数组进行排序.我使用qsort和一个简单的比较函数.
>扫描阵列以查找最长的重复值序列.
>如果此序列不在开头,请将值移动到位并在开始时创建序列.
>从上一步结束开始重复扫描过程,直到不再有任何重复序列.

这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int int_cmp(const void *p1,const void *p2) {
    int i1 = *(const int *)p1;
    int i2 = *(const int *)p2;
    return (i1 > i2) - (i1 < i2);
}

void print_array(const char *msg,const int *a,int n) {
    printf("%s: ",msg);
    for (int i = 0; i < n; i++)
        printf("%d%c",a[i]," \n"[i == n - 1]);
}

int main(int argc,char *argv[]) {
    int N = argc > 1 ? atoi(argv[1]) : 200;
    int *array;

    if (N <= 0 || (array = calloc(N,sizeof(*array))) == NULL)
        return 1;

    srand(N);
    for (int i = 0; i < N; i++) {
        unsigned int x = rand();
        array[i] = x * x % 10;
    }

    print_array("unsorted",array,N);
    qsort(array,N,sizeof(int),int_cmp);
    print_array("  sorted",N);
    /* sort by decrasing frequency (assuming N > 0) */
    for (int i = 0;;) {
        /* find the most repeated sequence in [i..N-1] */
        int rep = array[i];
        int n = 1,k;
        for (j = k = i + 1; j < N; j++) {
            if (array[j] == array[j - n]) {
                rep = array[j];
                k = j + 1;
                n++;
            }
        }
        if (n == 1) {
            /* no more duplicates,f-sort completed */
            break;
        }
        i += n;
        if (k > i) {
            /* shift the repeated sequence in place */
            while (k-- > i) {
                array[k] = array[k - n];
            }
            while (n-- > 0) {
                array[k--] = rep;
            }
        }
    }
    print_array("f-sorted",N);
    free(array);
    return 0;
}

按C中元素出现频率的降序排列数组

解决方法

猜你在找的C&C++相关文章