V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
askJavaJob
V2EX  ›  C

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

  •  1
     
  •   askJavaJob · 2018-09-08 11:30:36 +08:00 · 3021 次点击
    这是一个创建于 2028 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    12 条回复    2018-09-09 13:24:25 +08:00
    gyber
        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
    然后对这个结构体数组排序
    mjikop1231
        2
    mjikop1231  
       2018-09-08 12:36:35 +08:00 via iPhone
    @gyber 那第一个 nlogn 的意义何在
    changnet
        3
    changnet  
       2018-09-08 12:50:27 +08:00 via Android
    这根本不是数组排序。而是按重复降序排列。要是我就不会用这个数据结构。而是记录数字和重复次数再排序。如果源数据是这数组格式,就分析下再排序
    d18
        4
    d18  
       2018-09-08 12:55:36 +08:00
    遍历一遍,table 记录每个数字的出现次数,记下次数范围。
    如果范围不大,对 table 进行桶排序。
    遍历排序后的 table 即可。
    时间复杂度 O(N)。
    askJavaJob
        5
    askJavaJob  
    OP
       2018-09-08 13:25:54 +08:00
    @gyber 这不够黑科技,结构是不是要 new 出来啊?
    ,还要把结构里的数装回数组,代码老长了.
    gyber
        6
    gyber  
       2018-09-08 13:28:27 +08:00
    @mjikop1231 方便记录每个数字出现的个数
    如果直接用数组去记录比如 number[2]=4,数字太大时 number[10^999]就溢出了
    当然针对溢出,用 hash 之类的方法也可以处理
    不过排序是最方便的
    gyber
        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 输出就行了
    necomancer
        8
    necomancer  
       2018-09-08 14:15:47 +08:00
    1. 循环列表,构建一个 hashtable, 初始 T[item] = 0;
    2. 循环列表,T[item] += 1
    3. 按值排序 T, 方法具体找找 stackoverflow
    nilrust
        9
    nilrust  
       2018-09-08 14:59:07 +08:00
    无脑用 #8 楼的思路写就好了,代码如下:

    https://www.dooccn.com/c/#id/c3344c89e930d5fb926f091a95ec13bc
    qwlhappy
        10
    qwlhappy  
       2018-09-08 15:52:47 +08:00
    分两步
    先统计每个数字的出现次数,再对统计结果排序...
    msg7086
        11
    msg7086  
       2018-09-08 17:26:38 +08:00
    分两步
    先统计每个数字的出现次数,再把统计结果还原成数组。
    你都有压缩版的数组了还排序什么,直接解压啊。
    ayyll
        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)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3246 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:13 · PVG 20:13 · LAX 05:13 · JFK 08:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.