已知有个很长的int无序数组,要求不遍历比较整个数组,获得数组里最大的10个元素。
Java中怎么实现?或者其他语言
1
neoblackcap 2015-05-19 00:55:25 +08:00
不遍历是说要空间复杂度在O(n)之下?快排就可以了啦。当然这里的话,我觉得可能用堆排序会更好,毕竟建10次堆而已,应该会比快排全部排完快。
|
2
sandideas 2015-05-19 01:07:50 +08:00 via iPhone
@neoblackcap 确定你说的不是时间复杂度?快排的复杂度不是o(nlogn)么?
|
3
neoblackcap 2015-05-19 01:11:17 +08:00
@sandideas 是啊说错了,快排也记错了。不过我个人觉得这里用堆排序还是合理的建一次堆大概是要O(lg N),10次即可实现了吧,时间复杂度度为O(lg N),小于一次遍历。
|
4
ljcarsenal 2015-05-19 01:18:46 +08:00
top k 问题 搜一下就有了
|
5
SoloCompany 2015-05-19 01:40:57 +08:00 via iPad
问题就是错误的吧,不遍历怎么可能,应该是不排序吧
|
6
liuzhen OP |
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; } } ``` |
8
puncsky 2015-05-19 05:32:59 +08:00
第二种答案取返回值和右侧的部分就是了,忘了改。。。
|
11
zonghua 2015-05-19 09:04:45 +08:00 via iPhone
每当用人脑考量这种问题的时候,排序可是一门大学问。
|
12
aec4d 2015-05-19 09:07:22 +08:00
感觉和编程珠玑里面的第一章基本相似
|
13
wizardoz 2015-05-19 09:45:46 +08:00
用快速排序的变形,理想情况下log(N)。快排的复杂度是N×Log(N),但是这个场景不需要把整个数组都排序,只要把所有大于第十大的元素的数换到第十大数的左边就行。
参考《算法导论》第九章“中位数和顺序统计学”,或者参考快速排序,把其中不需要的交换去掉就行。 快速排序每次把数组的一个部分分成两个部分,然后分别在其中做同样的拆分操作。 而中位数的方法把一部分分成两部分以后,只在包含了结果的那一部分进行拆分,所以复杂度可以达到O(Log(N)) |
15
jadetang 2015-05-19 09:57:59 +08:00
你数组都不需要全部遍历一遍的?这有点不可能吧。
|
16
Charles0429 2015-05-19 10:03:42 +08:00
@neoblackcap 建堆的时间复杂度就是O(N),最后的时间复杂度至少是O(N)
|
17
Charles0429 2015-05-19 10:05:49 +08:00
@neoblackcap 不好意思,我搞错了,建堆的时间复杂度是10log10,请忽略。。
|
18
Charles0429 2015-05-19 10:09:44 +08:00
@Charles0429 再更正一下,建堆的时间复杂度是O(K),如果K是要建的初始堆大小的话
|
20
sandideas 2015-05-19 11:28:48 +08:00
|
22
puncsky 2015-05-19 13:05:10 +08:00
嗯说错了,第一个是 nlogk
|
23
song0071000 2015-05-19 19:26:26 +08:00
至少得遍历一边
|
24
Axurez 2015-05-20 14:19:25 +08:00
快速选择算法么
|
25
kaneg 2015-05-20 16:24:16 +08:00
无序数组遍历是最基本的操作,怎么可能不遍历。
|