215. 数组中的第K个最大元素
2023-07-03 本文已影响0人
红与树
题目
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入: [3,2,1,5,6,4], k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
解题思路
-
快速选择：快速排序的分区算法,平均时间复杂度为O(n),第
k大可以倒序分区。 - 哈希：使用数组哈希,也只会有一重循环遍历。
快速选择
class Solution {
public int findKthLargest(int[] nums, int k) {
//快速选择partition:快速排序的分区思想，快排的思想是一次找出一个数的正确位置，
// 并使得该数左边的元素都比它小，该数右边的元素都比它大，要找出第k
// 大的元素，只需要在快排的时候采用降序排序，找到下标为k-1的元素。
return quickSelect(0,nums.length-1,nums,k);//或者升序排序返回nums[n-k]
}
Random random = new Random();
int quickSelect(int start,int end,int[] nums,int k) {
//随机选一个数作为数轴 加速查找
int rand = start+random.nextInt(end-start+1), base = nums[rand];
swap(start,rand,nums);//放在开头位置
int index = start;
// 剩下元素依次与base比较，倒序排序,大的放前面
//3,2,1,5,6,4, k=2 : 1 5 6 4 3 2
for (int i = start + 1; i <= end; i++) {
if (nums[i] > base) swap(++index,i,nums);
//if (nums[i] >= base && ++index != i) swap(index,i,nums);
}
// base存放在区间开头，现在需要把它交换到index位置，即它在整个有序数组中的位置。
swap(index, start, nums);
// 如果index等于k-1已找到 小于k-1在右边区间查找,否则在左边
if(index == k-1) return nums[index];
else if (index < k-1) return quickSelect(index + 1, end, nums, k);
else return quickSelect(start, index - 1, nums, k);
}
void swap(int a,int b,int[] nums) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}
}
复杂度分析
- 时间复杂度：
O(n)，使用了随机化后规避了快速选择的特殊情况的最坏时间复杂度,平均时间复杂度O(n)。 - 空间复杂度：
O(n)，递归栈空间,也可以使用"二分查找式循环"优化空间到O(1)。
哈希
class Solution {
public int findKthLargest(int[] nums, int k) {
//哈希计数
int[] hash = new int[20001];
for(int i : nums) hash[i+10000]++;
int count = 0;
for(int i = hash.length-1,size = hash[i]; i >= 0; i--,size = hash[i]) {
while(size > 0) {
size --;
if(++count == k) return i-10000;
}
}
return -1;
}
}
复杂度分析
- 时间复杂度：
O(n)，一重循环遍历,其中n为20001。 - 空间复杂度：
O(n)，哈希数组空间。
