215 Kth Largest Element in an Array 數(shù)組中的第K個最大元素
Description:
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example:
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
題目描述:
在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 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 ≤ 數(shù)組的長度。
思路:
- 排序
時間復雜度O(nlgn), 空間復雜度O(1) - 小根堆
時間復雜度O(n), 空間復雜度O(n) - 快速排序
注意加入隨機數(shù)下標, 以保證時間復雜度最優(yōu)
時間復雜度O(n), 空間復雜度O(lgn)
代碼:
C++:
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int,vector<int>, less<int>> q;
for (int i = 0; i < nums.size(); i++) q.push(nums[i]);
while (k-- > 1) q.pop();
return q.top();
}
};
Java:
class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthLargest(nums, 0, nums.length - 1, k);
}
private int findKthLargest(int[] nums, int left, int right, int k) {
int index = partition(nums, left, right);
if (index + 1 == k) return nums[index];
if (index + 1 < k) return findKthLargest(nums, index + 1, right, k);
return findKthLargest(nums, left, index - 1, k);
}
private int partition(int[] nums, int left, int right) {
int random = (int)(Math.random() * (right - left + 1) + left), i = left, j = left + 1, temp = 0;
swap(nums, left, random, temp);
while (j <= right) {
if (nums[j] >= nums[left]) swap(nums, j, ++i, temp);
++j;
}
swap(nums, left, i, temp);
return i;
}
private void swap(int[] nums, int i, int j, int temp) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Python:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]
