求解一道很难的算法面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求解一道很难的算法面试题

求解一道很难的算法面试题# JobHunting - 待字闺中

S*C2013-10-06 07:10

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.

z*n2013-10-06 07:10

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.

p*p2013-10-06 07:10

3 楼

唔，LZ听说过quick sort么，这只是个变种

S*C2013-10-06 07:10

4 楼

谢谢！能写个pseudocode吗？不太懂具体怎么操作啊

【在 z***n 的大作中提到】

: 用nth_element先求最中间的那个数，然后两边分治
: 只递归Log(K)次，复杂度刚好

S*C2013-10-06 07:10

5 楼

谢谢！能写个pseudocode吗？不太懂具体怎么操作啊

【在 p*****p 的大作中提到】

: 唔，LZ听说过quick sort么，这只是个变种

s*n2013-10-06 07:10

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());
}

z*n2013-10-06 07:10

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吗？不太懂具体怎么操作啊

l*n2013-10-06 07:10

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

b*e2013-10-06 07:10

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] );