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

Question

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

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

然后将数组修改为：

   { 3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 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]);
    }
}

- Nit kt

---

你仅限于使用 C 吗？如果允许使用 C++，并且可以使用 std::map 和 qsort，那么你可以用 15 行代码完成它。 - mvp

阅读：[按频率排序元素|集2]（http://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/） - Grijesh Chauhan

是的，因为我完全不懂C++...但你可以向其他人建议使用C++。但我肯定无法理解那个。 - Nit kt

@Nitkt 你可以从这个答案如何按每个数字的频率降序排列数组？中选择一种技术。 - Grijesh Chauhan

@mvp 我尝试使用std :: map和pair，但最少也需要17行 :) - SynAck

Answer 1

按照值对数组进行排序；将结果进行RLE编码，将相等的每个跨度转换为元素和跨度长度的一对（您可以使用辅助数组来支持第二个组件）；按第二个组件的降序对这些对进行排序；即可得到您的结果。所有这些只需要O(n log n)的时间和O(n)的额外空间。

- Will Ness

Answer 2

我已经找到了一种优雅的方法来执行这种排序，最坏情况下的复杂度为O(N²)，平均复杂度为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", array, 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, j, 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", array, N);
    free(array);
    return 0;
}

- chqrlie

Answer 3

我用一些新的方法和逻辑非常简单高效地解决了这个问题。

def func(val):
    for key, value in dict1.items():
         if val == value:
             return key
res=[]        
for _ in range(int(input())):
    n=int(input())
    lst=list(map(int,input().split()))
    dict1={}
    lst.sort()
    lst2=[]
    for i in lst:
        dict1[i]=lst.count(i)
        lst2.append(lst.count(i))
    lst2.sort()
    lst2.reverse()
    s=''
    for i in lst2:
        k=func(i)
        s=s+((str(k)+" ")*i)
        dict1[k]=0
    s1=s.replace('None',"")
    s2=s1.replace("  ","")
    res.append(s2)
for i in res:
    print(i)

- Nandini Ashok Tuptewar

Answer 4

这里有一个使用qsort实现的排序值以便于计算频率的方法，并将结果频率表按降序排序。当两个值具有相同的频率时，我们按递增值排序。

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

int cmp_int(const void *p1, const void *p2) {
    return *(const int *)p1 - *(const int *)p2;
}

typedef struct {
    int val;
    int cnt;
} freq;

int cmp_freq(const void *p1, const void *p2) {
    const freq *pf1 = (const freq *)p1;
    const freq *pf2 = (const freq *)p2;
    if(pf1->cnt == pf2->cnt)
        return pf1->val - pf2->val;
    return pf2->cnt - pf1->cnt;
}

void frequencySort(int tbl[], int n) {
    // sort values in ascending order
    qsort(tbl, n, sizeof(int), cmp_int);

    // fill frequency table with frequencies
    int nFreq = 0;
    freq *freqTbl = malloc(n*sizeof(freq));
    int val = tbl[0];
    int cnt = 1;
    for(int i = 1; i < n; i++) {
        if(tbl[i] != val) {
            freqTbl[nFreq].cnt = cnt;
            freqTbl[nFreq].val = val;
            nFreq++;
            val = tbl[i];
            cnt = 1;
        } else {
            cnt++;
        }
    }
    freqTbl[nFreq].cnt = cnt;
    freqTbl[nFreq].val = val;
    nFreq++;

    // sort by frequencies
    qsort(freqTbl, nFreq, sizeof(freq), cmp_freq);    

    // refill tbl by frequencies
    int m = 0;
    for(int i = 0; i < nFreq; i++)
        for(int j = 0; j < freqTbl[i].cnt; j++)
            tbl[m++] = freqTbl[i].val;

    free(freqTbl);
}

int main(int argc, char *argv[])
{
    int n = argc > 1 ? atoi(argv[1]) : 200;
    int *tbl;
    if (n <= 0 || (tbl = malloc(n * sizeof(int))) == NULL)
        return 1;
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        tbl[i] = abs(rand()) % 10;

    printf("[%d", tbl[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", tbl[i]);
    printf("]\n");

    frequencySort(tbl, n);

    printf("[%d", tbl[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", tbl[i]);
    printf("]\n");

    free(tbl);
    return 0;
}

- chmike

---

请注意，两个整数相减的使用对于小数字是可以的（而且代码只测试0..9范围内的数字，这是“小数字”的典型案例），但如果数据中既有大正数又有大负数，则会遇到整数溢出问题。在 cmp_freq() 中，一种选项可能是使用：return (pf1->val > pf2->val) - (pf1->val < pf2->val);，以及类似地，在 cmp_freq() 中进行其他比较以及在 cmp_int() 中的比较。 - Jonathan Leffler

Answer 5

你可以从修改过的桶排序开始，但是在创建桶列表后停止。

我受到桶排序的启发制作了这个算法。它最薄弱的环节是快速排序，但是可以修改为使用桶排序。我估计对于长度为n且最大值为m的数组A，其复杂度为O(m + n log n)，如果使用桶排序进行修改，则会降至O(m+n)。

typedef struct {
    int bucket;
    int index;
} element;

int compare(const void *a, const void *b)
{
    element *A = (element *) a;
    element *B = (element *) b;
    return(A->bucket < B->bucket);
}

void sortByFreq(int * arr, int len)
{
    int arrMax=findMax(arr, len);  // O(len)
    element x[arrMax+1];
    for(int i=0; i<=arrMax; i++) {   // O(arrMax)
        x[i].bucket=0;
        x[i].index=i;
    }
    for(int i=0; i<len; i++)   // O(len)
       x[arr[i]].bucket++;
    qsort(x, arrMax+1, sizeof(element), compare);  //O(len*log(len))

    int k=0;
    for(int i=0; i<=arrMax; i++)  // O(arrMax + len)
        for(int j=0; j<x[i].bucket; j++)
            arr[k++]=x[i].index;
}

- klutt

---

我认为如果需要排序的数组的所有元素都是负数（或稍微有点不同，如果任何一个元素是负数），或者整数的大小是巨大的（例如10亿到20亿），那么这段代码就会遇到问题，因为它的数组定义为“element x[arrMax + 1];”。 - Jonathan Leffler

@JonathanLeffler 是的，如果你没有足够的内存，它会在处理非常大的数字时遇到问题。但是，只需添加最小数的偏移量就可以很容易地修改它以处理负数。 - klutt

Answer 6

1. 创建一个二叉搜索树，并在创建BST时维护每个元素的出现频率计数。如果使用自平衡BST，则此步骤可能需要O(nLogn)时间。
2. 对BST进行中序遍历，并将每个元素及其计数存储在辅助数组中。让我们称辅助数组为'count []'。请注意，该数组的每个元素都是元素和频率对。此步骤需要O(n)时间。
3. 按元素频率对“count []”进行排序。如果使用O(nLogn)排序算法，则此步骤需要O(nLogn)时间。
4. 遍历排序后的数组'count []'。对于每个元素x，打印它'freq'次，其中'freq'是x的频率。此步骤需要O(n)时间。

如果使用O(nLogn)排序算法并使用具有O(Logn)插入操作的自平衡BST，则算法的总时间复杂度可以最小化为O(nLogn)。

Geeks for Geeks

- SynAck

Answer 7

#include<stdio.h>
#include<malloc.h>
int* freq_sort_array(int*,int);
int main()
{
  int a[10]={7,0,0,5,0,0,0,0,0,0};     /*input array*/
  int *b,i;
  printf("Input Array\n");
  for(i=0;i<10;i++)
  printf("%d ",a[i]);
  b=freq_sort_array(a,10);
  printf("\nOutput array\n");
  for(i=0;i<10;i++)
  printf("%d ",b[i]);
}

                                       /*Function for sorting array based on frequency*/
int* freq_sort_array(int *a,int len)
{
  int i,j,temp,count,k=0,s=0,t=0;
  int *b=(int*)malloc(len*sizeof(int));
  int *c=(int*)malloc(len*sizeof(int));
  for(i=0;i<len;i++)
  {
      for(j=i+1;j<len;j++)
      {
          if(a[j]==a[i])
          {
            temp=a[j];
            for(j;j>i+1;j--)
            {
             a[j]=a[j-1];
            }
            a[++i]=temp;
          }
      }
  }
  for(i=0;i<len;i++)
  {
      a[j]=a[i];
      count=1;
      if(i!=len-1)
      {
          while(a[++i]==a[j]&& i<len)
            count++;
          i=i-1;
      }
      b[k]=a[j];
      c[k++]=count;
  }
  for(i=1;i<k;i++)
  {
      for(j=0;j<k-i;j++)
      {
          if(c[j]<c[j+1])
          {
              c[j]=c[j]+c[j+1]-(c[j+1]=c[j]);
              b[j]=b[j]+b[j+1]-(b[j+1]=b[j]);
          }
      }
  }
  for(i=0;i<k;i++)
  {
      for(j=0;j<c[i];j++)
        a[s++]=b[i];
  }
 return a;
}

- MOHAMMED A J

---

除非您明确使用了<malloc.h>提供的额外功能（而此代码没有），否则请使用<stdlib.h>（而不是<malloc.h>）声明malloc()等函数。 - Jonathan Leffler

我的编译器对这两行代码 c[j]=c[j]+c[j+1]-(c[j+1]=c[j]); 和 b[j]=b[j]+b[j+1]-(b[j+1]=b[j]); 报错，因为它们在赋值给 c[j+1] 的同时也使用了它，而且处理顺序没有定义（没有序列点来使其正常工作）。此外，该代码还存在内存泄漏问题。它分配了 b 和 c 两个数组（并没有检查分配是否成功），在返回前也没有释放它们。我不清楚这些可疑的赋值语句是做什么用的 - 我不能推荐这段代码。它可能在某些系统上能够工作，但不可靠。 - Jonathan Leffler