问题是根据频率对数组进行排序
元素.例如,如果输入数组是
元素.例如,如果输入数组是
{ 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; }
