[算法] [leetcode-215] 数组中的第K个最大元素

215 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你必要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法办理此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums <= 104

---

···
class Solution {
public void swapArray(int[] nums, int i, int j) {
if (i == j || i > nums.length || i < 0 || j > nums.length || j < 0) {
return;
}
int tmp = nums;
nums = nums[j];
nums[j] = tmp;
}

1.     public int findKthLargest(int[] nums, int k) {
2.         if (k <= 0 && k > nums.length) {
3.             return -1;
4.         }
5.         int begin = 0;
6.         int end = nums.length - 1;
7.         // 注意此处是升序排列. 真正获取需要进行反转求下标.
8.         int endIndex = nums.length - k;
9.         while (begin <= end) {
10.             int randomNum = begin + new Random().nextInt(end - begin+1 );
11.             System.out.println(randomNum);
12.             int[] rangeArray = chessSort(nums, begin, end, randomNum);
13.             if (rangeArray[0] <= endIndex && rangeArray[1] >= endIndex) {
14.                 return nums[endIndex];
15.             } else if (endIndex < rangeArray[0]) {
16.                 end = rangeArray[0] - 1;
17.             } else if (endIndex > rangeArray[1]) {
18.                 begin = rangeArray[1] + 1;
19.             }
20.         }
21.         return -1;
22.     }
24.     public int[] chessSort(int[] nums, int begin, int end, int k) {
25.         if (begin > end) {
26.             return new int[]{-1, -1};
27.         }
28.         if (begin == end) {
29.             return new int[]{begin, end};
30.         }
31.         int beginIndex = begin - 1;
32.         int endIndex = end + 1;
33.         int index = begin;
34.         int flagNum = nums[k];
35.         while (index < endIndex) {
36.             if (nums[index] == flagNum) {
37.                 index++;
38.             } else if (nums[index] < flagNum) {
39.                 // 扩展左边界
40.                 beginIndex = beginIndex + 1;
41.                 // 交换当前数字
42.                 swapArray(nums, index, beginIndex);
43.                 // 指标指向下一位
44.                 index = index + 1;
45.             } else if (nums[index] > flagNum) {
46.                 // 扩展有边界
47.                 endIndex = endIndex - 1;
48.                 // 交换
49.                 swapArray(nums, index, endIndex);
50.                 // 指标不动 注意: 当前数字还未进行比较
51.                 index = index;
52.             }
53.         }
54.         return new int[]{beginIndex + 1, endIndex - 1};
55.     }
56. }

复制代码

···

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。