S*******C
发帖数: 822 | 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***n
发帖数: 11 | 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*****p
发帖数: 379 | 3 唔，LZ听说过quick sort么，这只是个变种 | S*******C
发帖数: 822 | 4 谢谢！能写个pseudocode吗？不太懂具体怎么操作啊
【在 z***n 的大作中提到】
: 用nth_element先求最中间的那个数，然后两边分治
: 只递归Log(K)次，复杂度刚好
| S*******C
发帖数: 822 | 5 谢谢！能写个pseudocode吗？不太懂具体怎么操作啊
【在 p*****p 的大作中提到】
: 唔，LZ听说过quick sort么，这只是个变种
| s*******n
发帖数: 305 | 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; i
if (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***n
发帖数: 11 | 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*n
发帖数: 529 | 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***e
发帖数: 1419 | 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] );
|
|
