HackMD
215.Kth Largest Element in an Array
tags: Medium Array Divide and Conquer Sorting Heap
215. Kth Largest Element in an Array
題目描述
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
範例
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
- 1 <=
k<=nums.length<= 105 - -104 <=
nums[i]<= 104
解答
Python
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
data = nums[:k]
heapq.heapify(data)
for num in nums[k:]:
heapq.heappushpop(data, num)
return min(data)
Yen-Chi ChenMon, Aug 14, 2023
TypeScript
- quick select
partition 函式會回傳一個 pivot，這個 pivot 左邊的元素都比 pivot 大，右邊的元素都比 pivot 小，不斷呼叫 partition 然後每次檢查 pivot 的位置是否為 k - 1，如果是的話就回傳 pivot 的值。
function partition(arr: number[], left: number, right: number) {
const pivot = arr[right];
while (left < right) {
while (left < right && arr[left] >= pivot) {
left++;
}
arr[right] = arr[left];
while (left < right && arr[right] <= pivot) {
right--;
}
arr[left] = arr[right];
}
arr[right] = pivot;
return left;
}
function findKthLargest(nums: number[], k: number): number {
let low = 0;
let high = nums.length - 1;
let pivot = partition(nums, low, high);
while (pivot !== k - 1) {
if (pivot > k - 1) {
high = pivot - 1;
pivot = partition(nums, low, high);
} else {
low = pivot + 1;
pivot = partition(nums, low, high);
}
}
return nums[pivot];
}
- counting sort
function findKthLargest(nums: number[], k: number): number {
const n = nums.length;
let max = nums[0];
let min = nums[0];
for (const num of nums) {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
const size = max - min + 1;
const buckets = new Array(size).fill(0);
for (let i = 0; i < n; i++) {
buckets[nums[i] - min]++;
}
let remain = k;
for (let i = size - 1; i >= 0; i--) {
remain -= buckets[i];
if (remain <= 0) {
return i + min;
}
}
return -1;
}
SheepMon, Aug 14, 2023
C++
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> kthFinder;
for (int num : nums) {
kthFinder.push(num);
while (kthFinder.size() > k) {
kthFinder.pop();
}
}
return kthFinder.top();
}
};
Jerry Wu14 Aug 2023
