V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
marginleft
V2EX  ›  问与答

给定一个 int 数组,长度 200,里面的元素是 0-2000 内的随机数。找出 50-100 之间的所有数,并排序。大家有什么思路?

  •  
  •   marginleft · 2015-07-09 16:36:41 +08:00 · 2994 次点击
    这是一个创建于 2646 天前的主题,其中的信息可能已经有所发展或是发生改变。
    第 1 条附言  ·  2015-07-10 09:13:00 +08:00
    感谢大家回复。
    我一开始也想用bitset,来初始化一个长度是2000的数组。但是后来看到大家的初始化max-min=50个桶就能解决,感觉这确实是一个很好的方法,我用java写了一个demo:

    import java.util.Arrays;
    import java.util.Random;

    public class SortTest {
    public static void main(String[] args) {
    // 初始化
    int inputArrLength = 200;
    int maxValue = 2000;
    int min = 50, max = 100;

    int input[] = new int[inputArrLength];
    Random rand = new Random();
    System.out.println("input:");
    for (int i = 0; i < input.length; i++) {
    input[i] = rand.nextInt(maxValue);
    if (input[i] >= min && input[i] < max) {
    System.out.print(input[i] + ",");
    }
    }
    System.out.println();

    // bitset排序
    int bitset[] = new int[maxValue];
    Arrays.fill(bitset, 0);
    for (int i : input) {
    if (i >= min && i < max) {
    bitset[i]++;
    }
    }
    for (int i = 0; i < bitset.length; i++) {
    if (bitset[i] > 0) {
    for (int j = 0; j < bitset[i]; j++) {
    System.out.print(i + ",");
    }
    }
    }
    System.out.println();
    // 桶排序
    int bucket[] = new int[max - min];
    Arrays.fill(bucket, 0);
    for (int i : input) {
    if (i >= min && i < max) {
    bucket[i - min]++;
    }
    }
    for (int i = 0; i < bucket.length; i++) {
    if (bucket[i] > 0) {
    for (int j = 0; j < bucket[i]; j++) {
    System.out.print((i + min) + ",");
    }
    }
    }
    }
    }
    25 条回复    2015-07-10 13:23:38 +08:00
    sumhat
        1
    sumhat  
       2015-07-09 16:42:52 +08:00
    先排个序再找 50 - 100 的就好了
    loveuqian
        2
    loveuqian  
       2015-07-09 16:43:00 +08:00 via iPhone
    初学者只能想到先遍历找出再排序了
    batman2010
        3
    batman2010  
       2015-07-09 16:46:17 +08:00
    最大堆。
    txx
        4
    txx  
       2015-07-09 16:51:24 +08:00
    2000 直接做基数排序吧....
    chlx
        5
    chlx  
       2015-07-09 16:52:22 +08:00
    如果不重复的话bit记录50-100. 最后按顺序输出. O(N).
    publicID001
        6
    publicID001  
       2015-07-09 16:57:21 +08:00 via Android
    统计50-100 之间的所有数出现次数,输出

    另外这种数据规模就算暴力也没什么压力啊
    Kilerd
        7
    Kilerd  
       2015-07-09 16:58:36 +08:00
    先sort,再用二分法找50和100,就可以了吧
    otakustay
        8
    otakustay  
       2015-07-09 17:15:12 +08:00
    才200个数,显然开200个空位直接哈希排序了,冲撞就用开链表解决
    akira
        9
    akira  
       2015-07-09 17:46:07 +08:00
    这个数据量,随便什么方法都可以了呀。
    先排序在过滤或者先过滤再排序都毫无压力的。
    而且排序直接冒泡都没问题呀
    also24
        10
    also24  
       2015-07-09 17:59:32 +08:00
    我可以推荐一下Bogo排序嘛?
    scream7
        11
    scream7  
       2015-07-09 18:17:47 +08:00
    计数排序.
    18000rpm
        12
    18000rpm  
       2015-07-09 18:58:50 +08:00 via Android
    想到快排,并且在每次分区的过程中遇到 50~100 之外的直接丢掉。
    leavic
        13
    leavic  
       2015-07-09 20:06:57 +08:00
    @sumhat 运算量上讲,先查找再排序比较快吧。
    acros
        14
    acros  
       2015-07-09 20:43:59 +08:00
    空间换时间吗?遍历一遍。

    声明一个200长度的数组numArray[200],memset一下。
    遍历一遍numArray[i]++,就得到所有数的排序表了
    acros
        15
    acros  
       2015-07-09 20:44:58 +08:00
    上面数字说错了。等下我改改。
    acros
        16
    acros  
       2015-07-09 20:48:54 +08:00
    numArray[2000];
    原数组遍历src[i],
    numArray[src[i]]++

    然后查看下numArray从50到100项非零的。
    hahastudio
        17
    hahastudio  
       2015-07-09 20:51:48 +08:00
    桶排啊,反正就 51 个位置
    cloud107202
        18
    cloud107202  
       2015-07-09 21:23:09 +08:00
    桶排+1
    IwfWcf
        19
    IwfWcf  
       2015-07-09 22:42:36 +08:00
    才 200 长度,怎么搞都可以啦……
    liuhaotian
        20
    liuhaotian  
       2015-07-09 22:44:40 +08:00 via iPhone
    数组[50,100] x[M]++
    msg7086
        21
    msg7086  
       2015-07-09 22:49:42 +08:00
    最容易实现的方法就是堆排序了吧。开个priority queue什么的然后一边判断一边插♂,跑完就能拿到结果了。
    lzdhlsc
        22
    lzdhlsc  
       2015-07-10 01:54:56 +08:00
    桶排 O(n)
    initdrv
        23
    initdrv  
       2015-07-10 02:26:56 +08:00 via iPhone
    身为一名默默无闻的JAVA新手,表示只能想到用Arrays的sort排序后,再用二分查找?分别得到不小于50和不大于100的角标?最后循环输出?😔😳
    poke707
        24
    poke707  
       2015-07-10 12:41:30 +08:00
    LZ其实使用了twitter sort的一个变种
    https://github.com/ExPHAT/twitter-sort
    marginleft
        25
    marginleft  
    OP
       2015-07-10 13:23:38 +08:00
    @poke707 为什么这么说呢?
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2290 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 45ms · UTC 03:51 · PVG 11:51 · LAX 20:51 · JFK 23:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.