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

问个排序问题

  •  
  •   liuzhen ·
    liuzhen9327 · 2015-05-19 00:42:39 +08:00 · 3382 次点击
    这是一个创建于 3471 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知有个很长的int无序数组,要求不遍历比较整个数组,获得数组里最大的10个元素。

    Java中怎么实现?或者其他语言

    25 条回复    2015-05-20 16:24:16 +08:00
    neoblackcap
        1
    neoblackcap  
       2015-05-19 00:55:25 +08:00
    不遍历是说要空间复杂度在O(n)之下?快排就可以了啦。当然这里的话,我觉得可能用堆排序会更好,毕竟建10次堆而已,应该会比快排全部排完快。
    sandideas
        2
    sandideas  
       2015-05-19 01:07:50 +08:00 via iPhone
    @neoblackcap 确定你说的不是时间复杂度?快排的复杂度不是o(nlogn)么?
    neoblackcap
        3
    neoblackcap  
       2015-05-19 01:11:17 +08:00
    @sandideas 是啊说错了,快排也记错了。不过我个人觉得这里用堆排序还是合理的建一次堆大概是要O(lg N),10次即可实现了吧,时间复杂度度为O(lg N),小于一次遍历。
    ljcarsenal
        4
    ljcarsenal  
       2015-05-19 01:18:46 +08:00
    top k 问题 搜一下就有了
    SoloCompany
        5
    SoloCompany  
       2015-05-19 01:40:57 +08:00 via iPad
    问题就是错误的吧,不遍历怎么可能,应该是不排序吧
    liuzhen
        6
    liuzhen  
    OP
       2015-05-19 01:54:10 +08:00
    @ljcarsenal 感谢~ 果然万能的v2~

    http://www.cnblogs.com/luxiaoxun/archive/2012/09/11/2679743.html

    昨天电面被问到了
    puncsky
        7
    puncsky  
       2015-05-19 05:32:17 +08:00   ❤️ 1
    两种做法

    一是用 minheap,在 Java 里就是 PriorityQueue,O(logn) time, O(k) space

    ``` java
    public class LargestKIntegers {
    public class TopList<T extends Comparable<T>> {
    private final int _capacity;
    private final PriorityQueue<T> _minHeap;

    public TopList(int capacity) {
    _capacity = capacity + 1;
    _minHeap = new PriorityQueue<T>(capacity);
    }

    public void add(T nextValue) {
    _minHeap.offer(nextValue);
    if (_minHeap.size() >= _capacity) _minHeap.poll();
    }

    public Collection<T> getTop() {
    return new ArrayList<T>(_minHeap);
    }
    }

    @Test
    public void keepLargest5() {
    TopList<Integer> list = new TopList<Integer>(5);
    for (int i = 0; i < 10; i++) {
    list.add(i);
    }
    for (int i = -1; i >= -100; i--) {
    list.add(i);
    }
    Collection<Integer> rst = list.getTop();

    Assert.assertEquals(5, rst.size());
    for (int i = 5; i < 10; i++) {
    Assert.assertTrue(rst.contains(i));
    }
    }
    }

    ```

    第二种做法是类似 quick sort 里面的 partition


    ``` java
    // Use partition in quicksort
    // Expected: N + N/2 + N/4 + ... = N
    // Worst-case: N^2
    // Side effect: largest K integers will be in [K... N-1] subarray
    public class KthLargestElement {
    public int kthLargestElement(int k, ArrayList<Integer> numbers) {
    int rank = partition(numbers, 0, numbers.size() - 1);
    while (rank != k) {
    if (rank < k) {
    rank = partition(numbers, rank-1 + 1, numbers.size() - 1);
    } else {
    rank = partition(numbers, 0, rank-1 - 1);
    }
    }

    return numbers.get(rank-1);
    }

    int partition(List<Integer> a, int s, int e) {
    int j = s;
    int midVal = a.get(e);
    for (int i = s; i <= e; i++) {
    if (a.get(i) >= midVal) {
    int tmp = a.get(j);
    a.set(j, a.get(i));
    a.set(i, tmp);
    j++;
    }
    }
    return j;
    }
    }
    ```
    puncsky
        8
    puncsky  
       2015-05-19 05:32:59 +08:00
    第二种答案取返回值和右侧的部分就是了,忘了改。。。
    emitvoice
        9
    emitvoice  
       2015-05-19 07:04:42 +08:00
    @puncsky mk, read it later.
    njustyw
        10
    njustyw  
       2015-05-19 08:34:46 +08:00 via Android
    @puncsky 时间复杂度是O(n.logk)吧
    zonghua
        11
    zonghua  
       2015-05-19 09:04:45 +08:00 via iPhone
    每当用人脑考量这种问题的时候,排序可是一门大学问。
    aec4d
        12
    aec4d  
       2015-05-19 09:07:22 +08:00
    感觉和编程珠玑里面的第一章基本相似
    wizardoz
        13
    wizardoz  
       2015-05-19 09:45:46 +08:00
    用快速排序的变形,理想情况下log(N)。快排的复杂度是N×Log(N),但是这个场景不需要把整个数组都排序,只要把所有大于第十大的元素的数换到第十大数的左边就行。

    参考《算法导论》第九章“中位数和顺序统计学”,或者参考快速排序,把其中不需要的交换去掉就行。

    快速排序每次把数组的一个部分分成两个部分,然后分别在其中做同样的拆分操作。
    而中位数的方法把一部分分成两部分以后,只在包含了结果的那一部分进行拆分,所以复杂度可以达到O(Log(N))
    wizardoz
        14
    wizardoz  
       2015-05-19 09:50:28 +08:00
    @wizardoz 不好意思,脑子糊了 复杂度应该是 O(N)才对。而minheap的方法复杂度是 O(Nlog10)
    jadetang
        15
    jadetang  
       2015-05-19 09:57:59 +08:00
    你数组都不需要全部遍历一遍的?这有点不可能吧。
    Charles0429
        16
    Charles0429  
       2015-05-19 10:03:42 +08:00
    @neoblackcap 建堆的时间复杂度就是O(N),最后的时间复杂度至少是O(N)
    Charles0429
        17
    Charles0429  
       2015-05-19 10:05:49 +08:00
    @neoblackcap 不好意思,我搞错了,建堆的时间复杂度是10log10,请忽略。。
    Charles0429
        18
    Charles0429  
       2015-05-19 10:09:44 +08:00
    @Charles0429 再更正一下,建堆的时间复杂度是O(K),如果K是要建的初始堆大小的话
    liuzhen
        19
    liuzhen  
    OP
       2015-05-19 10:27:11 +08:00
    @jadetang 可以遍历。我题上写的是不遍历比较,用计数算法可以算出来
    sandideas
        20
    sandideas  
       2015-05-19 11:28:48 +08:00
    @liuzhen 果然是我理解错了。。
    我一直不敢回答。。总觉得,怎么可能不遍历就可以求最大。
    不遍历,都不知道下一个是不是最大的,又怎么判断这个是最大的。。
    如果可以遍历的话,维护一个堆应该是最快的了
    puncsky
        21
    puncsky  
       2015-05-19 12:54:19 +08:00
    @njustyw // Expected: N + N/2 + N/4 + ... = N
    puncsky
        22
    puncsky  
       2015-05-19 13:05:10 +08:00
    嗯说错了,第一个是 nlogk
    song0071000
        23
    song0071000  
       2015-05-19 19:26:26 +08:00
    至少得遍历一边
    Axurez
        24
    Axurez  
       2015-05-20 14:19:25 +08:00
    快速选择算法么
    kaneg
        25
    kaneg  
       2015-05-20 16:24:16 +08:00
    无序数组遍历是最基本的操作,怎么可能不遍历。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5640 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 08:00 · PVG 16:00 · LAX 00:00 · JFK 03:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.