1 題目：數組中的第K個最大元素

官方標定難度：中

給定整數數組 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$

2 solution

直接用堆排序，找到 top - k

代碼

class Solution {
public:
int findKthLargest(vector<int> &nums, int k) {/** 維護大小為 k 的堆* 時間復雜度為 (n + k)logk*/priority_queue<int, vector<int>, greater<>> topK;for (int i: nums) {topK.push(i);if (topK.size() > k) topK.pop();}return topK.top();
}
};

結果

3 進階

用快速排序思路，只找第 k 個元素，即不需要完全排序。

代碼

class Solution {
public:int partition(vector<int> &nums, int left, int right) {if (right <= left) return left;int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] < pivot) {swap(nums[++i], nums[j]);}else if(nums[j] == pivot){if(rand() % 2){swap(nums[++i], nums[j]);}}}swap(nums[i + 1], nums[right]);return i + 1;
}int quickSelect(vector<int> &nums, int left, int right, int index) {int pivotIndex = partition(nums, left, right);if (pivotIndex == index) return nums[index];else if (pivotIndex > index) return quickSelect(nums, left, pivotIndex - 1, index);return quickSelect(nums, pivotIndex + 1, right, index);
}int findKthLargest(vector<int> &nums, int k) {/** 用快速選擇算法:* 即快速排序的思路*/return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};

結果