这是一个创建于 2304 天前的主题，其中的信息可能已经有所发展或是发生改变。
想了半天,没想好,各位帮帮忙. 把一个数组的数降序排列,重复的数排在前面,重复的越多排的越前. 比如; 22224443351
 |
1
gyber 2018-09-08 11:39:27 +08:00  2
先排序一次 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 然后对这个结构体数组排序 |
 |
2
mjikop1231 2018-09-08 12:36:35 +08:00 via iPhone
@gyber 那第一个 nlogn 的意义何在
|
 |
3
changnet 2018-09-08 12:50:27 +08:00 via Android
这根本不是数组排序。而是按重复降序排列。要是我就不会用这个数据结构。而是记录数字和重复次数再排序。如果源数据是这数组格式，就分析下再排序
|
 |
4
d18 2018-09-08 12:55:36 +08:00
遍历一遍，table 记录每个数字的出现次数，记下次数范围。
如果范围不大，对 table 进行桶排序。 遍历排序后的 table 即可。 时间复杂度 O(N)。 |
 |
5
askJavaJob OP @gyber 这不够黑科技,结构是不是要 new 出来啊?
,还要把结构里的数装回数组,代码老长了. |
|
6
gyber 2018-09-08 13:28:27 +08:00
@mjikop1231 方便记录每个数字出现的个数
如果直接用数组去记录比如 number[2]=4，数字太大时 number[10^999]就溢出了 当然针对溢出，用 hash 之类的方法也可以处理 不过排序是最方便的 |
|
7
gyber 2018-09-08 13:52:26 +08:00 via Android
@askJavaJob 这个问题，说难也难，说简单也简单
关键是这些数字的范围和类型要具体一点，我现在给的是一个最稳妥又比较快的办法 比如说这种数据 1 1.5 1.5 1.5 10^999 10^999 用我的方法就依然可以处理 但如果是 1 1 2 2 99 17 17 这样确保是整数而且比较小 用 num[v[i]]++记录每个数字出现次数，然后 for 一遍 num 输出就行了 |
 |
8
necomancer 2018-09-08 14:15:47 +08:00
1. 循环列表，构建一个 hashtable, 初始 T[item] = 0;
2. 循环列表，T[item] += 1 3. 按值排序 T, 方法具体找找 stackoverflow |
 |
9
nilrust 2018-09-08 14:59:07 +08:00
|
 |
10
qwlhappy 2018-09-08 15:52:47 +08:00
分两步
先统计每个数字的出现次数，再对统计结果排序... |
 |
11
msg7086 2018-09-08 17:26:38 +08:00
分两步
先统计每个数字的出现次数，再把统计结果还原成数组。 你都有压缩版的数组了还排序什么，直接解压啊。 |
 |
12
ayyll 2018-09-09 13:24:25 +08:00 via Android 1
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) |
Select Language