问个排序问题

[liuzhen]

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

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

[neoblackcap]

不遍历是说要空间复杂度在O(n)之下？快排就可以了啦。当然这里的话，我觉得可能用堆排序会更好，毕竟建10次堆而已，应该会比快排全部排完快。

[sandideas]

@neoblackcap 确定你说的不是时间复杂度？快排的复杂度不是o(nlogn)么？

[neoblackcap]

@sandideas 是啊说错了，快排也记错了。不过我个人觉得这里用堆排序还是合理的建一次堆大概是要O(lg N)，10次即可实现了吧，时间复杂度度为O(lg N),小于一次遍历。

[ljcarsenal]

top k 问题 搜一下就有了

[SoloCompany]

问题就是错误的吧，不遍历怎么可能，应该是不排序吧

[liuzhen]

@ljcarsenal 感谢~ 果然万能的v2~

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

昨天电面被问到了

[puncsky]

两种做法

一是用 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]

第二种答案取返回值和右侧的部分就是了，忘了改。。。

[emitvoice]

@puncsky mk, read it later.

[njustyw]

@puncsky 时间复杂度是O(n.logk)吧

[zonghua]

每当用人脑考量这种问题的时候，排序可是一门大学问。

[aec4d]

感觉和编程珠玑里面的第一章基本相似

[wizardoz]

用快速排序的变形，理想情况下log（N）。快排的复杂度是N×Log（N），但是这个场景不需要把整个数组都排序，只要把所有大于第十大的元素的数换到第十大数的左边就行。

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

快速排序每次把数组的一个部分分成两个部分，然后分别在其中做同样的拆分操作。
而中位数的方法把一部分分成两部分以后，只在包含了结果的那一部分进行拆分，所以复杂度可以达到O（Log（N））

[wizardoz]

@wizardoz 不好意思，脑子糊了 复杂度应该是 O（N）才对。而minheap的方法复杂度是 O（Nlog10）

[jadetang]

你数组都不需要全部遍历一遍的？这有点不可能吧。

[Charles0429]

@neoblackcap 建堆的时间复杂度就是O(N)，最后的时间复杂度至少是O(N)

[Charles0429]

@neoblackcap 不好意思，我搞错了，建堆的时间复杂度是10log10，请忽略。。

[Charles0429]

@Charles0429 再更正一下，建堆的时间复杂度是O(K)，如果K是要建的初始堆大小的话

[liuzhen]

@jadetang 可以遍历。我题上写的是不遍历比较，用计数算法可以算出来

[sandideas]

@liuzhen 果然是我理解错了。。
我一直不敢回答。。总觉得，怎么可能不遍历就可以求最大。
不遍历，都不知道下一个是不是最大的，又怎么判断这个是最大的。。
如果可以遍历的话，维护一个堆应该是最快的了

[puncsky]

@njustyw // Expected: N + N/2 + N/4 + ... = N

[puncsky]

嗯说错了，第一个是 nlogk

[song0071000]

至少得遍历一边

[Axurez]

快速选择算法么

[kaneg]

无序数组遍历是最基本的操作，怎么可能不遍历。