215. 数组中的第K个最大元素
难度:中等
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
解答:
class Solution {
//堆排序
//时间复杂度O(Nlogk)。空间复杂度O(k)
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
int len = nums.length;
for(int num : nums){
pq.offer(num);
if(pq.size() > k) pq.poll();
}
return pq.poll();
}
}
class Solution {
//先排序
//时间复杂度O(NlogN)。空间复杂度O(1)
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
class Solution {
//基于随机数的快排
//时间复杂度O(N)。空间复杂度O(logN)
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] nums, int left, int right, int index){
int randomIndex = randomPartition(nums, left, right);
if(randomIndex == index){
return nums[index];
}else{
return randomIndex < index ? quickSelect(nums, randomIndex + 1, right, index) : quickSelect(nums, left, randomIndex - 1, index);
}
}
public int randomPartition(int[] nums, int left, int right){
int randomIndex = random.nextInt(right - left + 1) + left;
swap(nums, randomIndex, right);
return partition(nums, left, right);
}
public int partition(int[] nums, int left, int right){
int temp = nums[right];
int index = left;
for(int i = left; i < right; i++){
if(nums[i] <= temp){
swap(nums, index, i);
index++;
}
}
swap(nums, index, right);
return index;
}
public void swap(int[] nums, int x, int y){
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}
参考自:
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。