Redian新闻
>
求解一道很难的算法面试题
avatar
求解一道很难的算法面试题# JobHunting - 待字闺中
S*C
1
Given an array A, the task is to find floor(n/k)th largest, floor(2n/k)th
largest, floor(3n/k)th largest,....and so on upto floor(kn/k)th largest.
Give an O(n*logk) algorithm.
avatar
z*n
2
用nth_element先求最中间的那个数,然后两边分治
只递归Log(K)次,复杂度刚好

【在 S*******C 的大作中提到】
: Given an array A, the task is to find floor(n/k)th largest, floor(2n/k)th
: largest, floor(3n/k)th largest,....and so on upto floor(kn/k)th largest.
: Give an O(n*logk) algorithm.

avatar
p*p
3
唔,LZ听说过quick sort么,这只是个变种
avatar
S*C
4
谢谢!能写个pseudocode吗?不太懂具体怎么操作啊

【在 z***n 的大作中提到】
: 用nth_element先求最中间的那个数,然后两边分治
: 只递归Log(K)次,复杂度刚好

avatar
S*C
5
谢谢!能写个pseudocode吗?不太懂具体怎么操作啊

【在 p*****p 的大作中提到】
: 唔,LZ听说过quick sort么,这只是个变种
avatar
s*n
6
用heap, nlogk
// T(nlgk), S(k+lgk)
public static void heapWay1(int[] num, int k) {
PriorityQueue heap = new PriorityQueue(k);
int size = k;
for (int i=0; iif (heap.size()heap.offer(num[i]);
else { // reach the size==k
if (num[i]<=heap.peek()) // smaller than root
continue;
else { // remove root, insert new one
heap.poll();
heap.offer(num[i]);
}
}
}
System.out.println("The top " + k + "largest values are:");
for (int i = 0; i System.out.print(heap.poll() + " ");
}
System.out.println(heap.size());
}
avatar
z*n
7
大概就这下面这样,其他是细节
// index[0,...,k-1]存放floor(n/k)...,用着方便
// result[0,...,k-1]依次存放结果
void get( int A[0,n-1], int index[0,k-1], int result[0,k-1] ){
int n = A.length, k = index.length;
if( k==0 ) return;
int privot = index[k/2];
nth_element( A, A+privot, A+n );
result[k/2] = A[privot];
get( A[0,privot-1], index[0,k/2-1], result[0,k/2-1] );
get( A[privot+1,n-1], index[k/2+1,k-1], result[k/2+1,k-1] );
}

【在 S*******C 的大作中提到】
: 谢谢!能写个pseudocode吗?不太懂具体怎么操作啊
avatar
l*n
8
鄙视看题都看不明白就上code的。

【在 s*******n 的大作中提到】
: 用heap, nlogk
: // T(nlgk), S(k+lgk)
: public static void heapWay1(int[] num, int k) {
: PriorityQueue heap = new PriorityQueue(k);
: int size = k;
: for (int i=0; i: if (heap.size(): heap.offer(num[i]);
: else { // reach the size==k
: if (num[i]<=heap.peek()) // smaller than root

avatar
b*e
9
You're assuming computing nth element is O(n), which is non-trivial.
I was more of thinking of using the O(n) median algorithm as a bridge.

【在 z***n 的大作中提到】
: 大概就这下面这样,其他是细节
: // index[0,...,k-1]存放floor(n/k)...,用着方便
: // result[0,...,k-1]依次存放结果
: void get( int A[0,n-1], int index[0,k-1], int result[0,k-1] ){
: int n = A.length, k = index.length;
: if( k==0 ) return;
: int privot = index[k/2];
: nth_element( A, A+privot, A+n );
: result[k/2] = A[privot];
: get( A[0,privot-1], index[0,k/2-1], result[0,k/2-1] );

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。