指定n个数字,找出其中大的k个数,这就是经典的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 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;
//因为数组下标是以0开始的,因此第k个的小标为k - 1,因此传入的为k - 1
int flag = RS(array, left, right, k - 1);
//返回值flag为第k个大值的下标,因此需要前k个大的值时,拷贝数组的范围是[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;
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。