題目描述

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設計并實現時間復雜度為 O(n) 的算法解決此問題。

題目分析

1. 根據題意分析，我們可以考慮使用快速排序算法來解決這個問題，但是由于快速排序的時間復雜度為nlog(n)，且當包含大量重復元素的數組時，時間復雜度會退化至 O(N^2),因此我們需要做一些優化處理：

我們在拆分的過程中，每輪遞歸劃分數組時，將數組劃分為三個部分：大于、等于和小于基準數。
如果劃分得到的基準數pivot對應的下標正好是我們需要的，則直接返回pivot；
如果pivot比目標值大，則遞歸左子數組，反之遞歸右子數組；
這樣就只需要遞歸一個區間就可以了。

2. 為了進一步提升算法的穩健性，我們采用隨機選擇的方式來選定基準數。

Code

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int pivot = nums[rand() % nums.size()];vector<int> big, equal, small;for (int num : nums) {if (num > pivot) {big.emplace_back(num);} else if (num < pivot) {small.emplace_back(num);} else {equal.emplace_back(num);}}if (k <= big.size()) {return findKthLargest(big,k);}if (nums.size() - small.size() < k) {return findKthLargest(small, k + small.size() - nums.size());}return pivot;}
};