成都网站建设推来客熊掌号,网页友情链接,济南 微网站,网站分成几种类型题目
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4…题目
给定整数数组 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 10^5-10^4 nums[i] 10^4 解答
源代码
class Solution {Random rand new Random();public int findKthLargest(int[] nums, int k) {return quickSelect(nums, k, 0, nums.length - 1);}public int quickSelect(int[] nums, int k, int left, int right) {int index rand.nextInt(right - left 1) left;// 目标值int target nums[index];// 因为在之后交换元素中nums[left]的值会被覆盖所以这里把nums[index]记为nums[left]的值nums[index] nums[left];int i left, j right;while (i j) {while (i j nums[j] target) {j--;}nums[i] nums[j];while (i j nums[i] target) {i;}nums[j] nums[i];}// 此时nums[i]前的元素都比目标值大nums[i]之后的元素都比目标值小nums[i] target;if (i k - 1) {return nums[i];} else if (i k - 1) {return quickSelect(nums, k, i 1, right);} else {return quickSelect(nums, k, left, i - 1);}}
}
总结
这道题写得我好痛苦……因为后面的测试案例有极端情况所以一定要用到随机又因为用到了随机所以和排序算法不是完全一样不能直接进行交换否则最后相遇的那个数和目标值交换后的数组不一定是合法的目标值前面都是大于它的数后面都是小于它的数。
