各位 V 友帮我想一个 c 数组算法

[askJavaJob]

想了半天,没想好,各位帮帮忙. 把一个数组的数降序排列,重复的数排在前面,重复的越多排的越前. 比如; 22224443351

[gyber]

先排序一次 nlogn，变成 12222334445
然后头到尾 for 一遍，一边 for 一边在另一个二维结构体里记录下：
[0].a=1
[0].b=1

[1].a=2
[1].b=4

[2].a=3
[2].b=2

[3].a=4
[3].b=3

[4].a=5
[4].b=1
然后对这个结构体数组排序

[mjikop1231]

@gyber 那第一个 nlogn 的意义何在

[changnet]

这根本不是数组排序。而是按重复降序排列。要是我就不会用这个数据结构。而是记录数字和重复次数再排序。如果源数据是这数组格式，就分析下再排序

[d18]

遍历一遍，table 记录每个数字的出现次数，记下次数范围。
如果范围不大，对 table 进行桶排序。
遍历排序后的 table 即可。
时间复杂度 O(N)。

[askJavaJob]

@gyber 这不够黑科技,结构是不是要 new 出来啊?
,还要把结构里的数装回数组,代码老长了.

[gyber]

@mjikop1231 方便记录每个数字出现的个数
如果直接用数组去记录比如 number[2]=4，数字太大时 number[10^999]就溢出了
当然针对溢出，用 hash 之类的方法也可以处理
不过排序是最方便的

[gyber]

@askJavaJob 这个问题，说难也难，说简单也简单

关键是这些数字的范围和类型要具体一点，我现在给的是一个最稳妥又比较快的办法

比如说这种数据
1
1.5
1.5
1.5
10^999
10^999

用我的方法就依然可以处理

但如果是
1 1 2 2 99 17 17 这样确保是整数而且比较小
用 num[v[i]]++记录每个数字出现次数，然后 for 一遍 num 输出就行了

[necomancer]

1. 循环列表，构建一个 hashtable, 初始 T[item] = 0;
2. 循环列表，T[item] += 1
3. 按值排序 T, 方法具体找找 stackoverflow

[nilrust]

无脑用 #8 楼的思路写就好了，代码如下：

https://www.dooccn.com/c/#id/c3344c89e930d5fb926f091a95ec13bc

[qwlhappy]

分两步
先统计每个数字的出现次数，再对统计结果排序...

[msg7086]

分两步
先统计每个数字的出现次数，再把统计结果还原成数组。
你都有压缩版的数组了还排序什么，直接解压啊。

[ayyll]

struct node {int num; int cnt;}
bool cmp(node a,node b){
if(a.cnt == b.cnt)return a.num>b.num;
return a.cnt > b.cnt;
}
node arr[n];
sort(arr,arr+n,cmp)