問題描述

在未排序的數組中找到第k個最大的元素。請注意，你需要找的是數組排序后的第k個最大的元素，而不是第k個不同的元素。

解題思路

解決這個問題有多種方法，下面是幾種常見的解題策略：

1. 排序后選擇: 將數組排序，然后選擇第len(array) - k位置上的元素。
2. 優先隊列(最小堆): 使用一個大小為k的最小堆，遍歷數組維護堆的大小為k，堆頂即為第k個最大元素。
3. 快速選擇(QuickSelect): 快速選擇算法是快速排序的變體，用于找到未排序數組中第k個最大的元素。

代碼示例

排序后選擇

class Solution:def findKthLargest(self, nums, k):nums.sort()return nums[-k]

這種方法的時間復雜度為O(NlogN)，空間復雜度為O(1)（如果使用的是原地排序算法）。

優先隊列(最小堆)

import heapqclass Solution:def findKthLargest(self, nums, k):heap = []for num in nums:heapq.heappush(heap, num)if len(heap) > k:heapq.heappop(heap)return heap[0]

這種方法的時間復雜度為O(NlogK)，空間復雜度為O(K)。

快速選擇(QuickSelect)

class Solution:def findKthLargest(self, nums, k):k = len(nums) - kdef quickselect(l, r):pivot, p = nums[r], lfor i in range(l, r):if nums[i] <= pivot:nums[p], nums[i] = nums[i], nums[p]p += 1nums[p], nums[r] = nums[r], nums[p]if p > k: return quickselect(l, p - 1)if p < k: return quickselect(p + 1, r)return nums[p]return quickselect(0, len(nums) - 1)

int partition(vector<int>& nums,int left,int right)
{int key = nums[left];while(left < right){while(left < right and nums[right] >= key ){right--;}nums[left] = nums[right]while(left < right and nums[left] <= key ){left++;}nums[right] = nums[left]}nums[left] = key; return left;  }int findk(vector<int>& nums)
{random_shuffle(nums.begin(),nums.end());int n = nums.size();int left = 0,rihgt = n-1;while(True){int p = partition(nums,left,right);if(p == n-k){return nums[p];}else if(p > n-k){right = p-1;}else{left = p +1;}}return -1;
}

?

快速選擇的平均時間復雜度為O(N)，最壞情況下的時間復雜度為O(N^2)，空間復雜度為O(1)。