返回信息流LZ最近初学数据结构和算法，面实习的时候有一道题是：
查找n个无序数(不重复)的最大k个数。考虑n很大时的时间复杂度。
应该咋做呢？用merge sort？
谢谢~~~~~~~~
----
感谢大家的回复！！就不一一回复感谢了。谢谢大家啊
我研究研究、尝试实现一下，做出来以后把代码贴出来
many thanks
----
选择排序的没大弄明白，带我在研究研究~
小顶堆的做出来了，也理解其时间复杂度了，代码如下：
public class TopK {
//develop a min heap of k numbers
public int[] initHeap(int[] all, int k){
int[] s = new int[k+1];
s[0] = k;
for(int i = 1;i <= k; i++){
s[i] = all[i];
}
int lastParent = s[0]/2;
for(int i = lastParent; i>0; i--){
this.rebuild(s, i);
}
return s;
}
//take every non-leaf node (parent node) into consideration, and rebuild
public void rebuild(int[] s, int p){
int last = s[0];
int l = p * 2;
int r = l+1;
int minLR = -1;
if(l > last && r > last){//System.out.println("check "+p);
return;
}
if(l <= last && r > last){
minLR = l;
}
if(r <= last){
minLR = s[l]>s[r]? r:l;
}
if(s[p] < s[minLR]){
return;
} else{
swap(s, p, minLR);
this.rebuild(s, minLR);
}
}
public void swap(int[] s, int p, int lr){
int temp = s[p];
s[p] = s[lr];
s[lr] = temp;
}
//consider numbers of s[k+1] ~ s[s.length], and compare each one with the root of k-min heap
public void compOthers(int[] topk, int[] all, int k){
for(int i = k+1; i<all.length; i++){
if(all[i] > topk[1]){
topk[1] = all[i];
this.rebuild(topk, 1);
}
}
}
public static void printArray(int[] s){
System.out.println("\n-------------------------");
System.out.printf("Index: ");
for(int i = 0; i < s.length; i++){
System.out.printf(i+" ");
}
System.out.printf("\nNumber: ");
for(Integer num:s){
System.out.printf(num+" ");
}
}
//s is the array and the top k numbers of it are needed. The first number of s (s[0]) is the number of numbers of s
public static void main(String[]args){
int[] s = new int[] { 14, 14, 2, 8, 3, 1, 6, 9, 4, 10, 11, 12, 13, 18, 5 };
int k = 7;
printArray(s);
TopK heap = new TopK();
int[] topk = heap.initHeap(s, k);
printArray(topk);
heap.compOthers(topk, s, k);
printArray(topk);
}
}
这是一条镜像帖。来源：北邮人论坛 / java / #48684同步于 2016/3/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
[求解]查找n个无序数的最大k个数
silenceTYN
2016/3/19镜像同步42 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
n很大有俩含义，除了字面意思之外还有个含义是远大于k，否则的话直接用快排，时间复杂度已经是最低了。
但是n远大于k就没必要把全部n个数都排序，只要建立一个大小为k的数组，从头到尾遍历，某个元素比这个数组里最小的数大的话就插入最小数的位置，这样貌似遍历一遍就能排出来？
通过『我邮2.0』发布
n很大的情况下，有O(n)时间复杂度的算法
int FindKthLargestUnknownLength(istringstream* sin, int k) {
vector<int> candidates;
int x;
while (*sin >> x) {
candidates.emplace_back(x);
if (candidates.size() == (k * 2) - 1) {
// Reorders elements about median with larger elements
// appearing before the median
nth_element(candidates.begin(), candidates.begin() + k - 1,
candidates.end(), greater<int>()); // O(k) time
candidates.resize(k);
}
}
// Find the k-th largest element in candidates
nth_element(candidates.begin(), candidates.begin() + k - 1,
candidates.end(), greater<int>());
return candidates[k - 1];
}
By using 2k - 1 as the array size, the time complexity of the selection algorithm is O(k). It is run every k - 1 elements, implying O(n) time complexity.
If a min-heap is used, containing the k largest elements seen thus far, the time complexity is O(nlogk).
【 在 silenceTYN 的大作中提到: 】
: LZ最近初学数据结构和算法，面实习的时候有一道题是：
: 查找n个无序数(不重复)的最大k个数。考虑n很大时的时间复杂度。
: 应该咋做呢？用merge sort？
: ...................