您好,登錄后才能下訂單哦!
指定n個數(shù)字,找出其中最大的k個數(shù),這就是經(jīng)典的TopK問題
public int[] topK(int[] array, int k) {
Arrays.sort(array);
return Arrays.copyOfRange(array, array.length - k, array.length);
}
public int[] topK(int[] array, int k) {
for(int i = 0; i < k; i++) {
for(int j = array.length - 1; j > 0; j--) {
if(array[j] > array[j - 1]) {
int tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
}
}
}
}
public Integer[] topK(int[] array, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0; i < k; i++) {
queue.add(array[i]);
}
for(int i = k; i < array.length; i++) {
if(array[i] > queue.peek()) {
queue.poll();
queue.add(array[i]);
}
}
return (Integer[])queue.toArray();
}
代碼:
public int[] topK5(int[] array, int k) {
int left = 0;
int right = array.length - 1;
//因為數(shù)組下標是以0開始的,因此第k個的小標為k - 1,因此傳入的為k - 1
int flag = RS(array, left, right, k - 1);
//返回值flag為第k個最大值的下標,因此需要前k個最大的值時,拷貝數(shù)組的范圍是[0, flag + 1)
return Arrays.copyOfRange(array, 0, flag + 1));
}
private int RS(int[] array, int left, int right, int k) {
if (left >= right) {
return left;
}
int index = partition(array, left, right);
int temp = index - left;
if(temp >= k) {
return RS(array, left, index - 1, k);
} else {
return RS(array, index + 1, right, k - index);
}
}
private int partition(int[] array, int left, int right) {
int tmp = array[left];
int l = left;
int r = right;
while(l < r) {
while(l < r && array[r] <= tmp) {
r--;
}
array[l] = array[r];
while(l < r && array[l] >= tmp) {
l++;
}
array[r] = array[l];
}
array[l] = tmp;
return l;
}
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。