无序数组找第K大的数
程序员文章站
2024-03-15 22:52:15
...
1、使用HashMap或者Queue保存
如果是少量的数据,比如K=2,3等可以使用,如2,保存到HashMap找最大,合计为2N次比较。
2、典型解法:快速排序分组。
在数组中找到第k大的元素
取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。
1.比基准大的元素数目标志位m正好为k-1,基准就是目的元素。
2.比基准大的元素标志位m小于k, 那么就在比基准小的集合里面找第(k-m)大的元素
3.若是比基准大的元素为m大于k,那就继续在该集合里面找第k大的元素。
如下是代码:
static void findKMax(int[] arr, int left, int right, int k) {
int temp = partition(arr, left, right);
if (temp == k - 1) {
System.out.println(arr[temp]);
} else if (temp > k - 1) {
findKMax(arr, left, temp - 1, k);
} else {
findKMax(arr, temp + 1, right, k - temp);
}
}
static int partition(int[] arr, int left, int right) {
int temp = arr[left];
while (left < right) {
while (temp >= arr[right] && left < right)
--right;
arr[left] = arr[right];
while (temp <= arr[left] && left < right)
++left;
arr[right] = arr[left];
}
arr[right] = temp;
return right;
}
public static void main(String[] args) {
int[] arr = new int[] { 12, 23, 2, 3, 2, 432, 43, 534, 5, 345, 3453, 53, 43 };
findKMax(arr,0,arr.length - 1,2);
}