0215. 數組中的第K個最大元素 · ttttt

# 0215. 數組中的第K個最大元素 ## 題目地址(215. 數組中的第K個最大元素) <https://leetcode-cn.com/problems/kth-largest-element-in-an-array/> ## 題目描述 ``` <pre class="calibre18">``` 在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序后的第 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 ≤ 數組的長度。 ``` ``` ## 前置知識 - 堆 - Quick Select ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路這道題要求在一個無序的數組中，返回第K大的數。根據時間復雜度不同，這題有3種不同的解法。 #### 解法一（排序）很直觀的解法就是給數組排序，這樣求解第`K`大的數，就等于是從小到大排好序的數組的第`(n-K)`小的數 (n 是數組的長度）。例如： ``` <pre class="calibre18">``` [3,2,1,5,6,4], k = 2 1. 數組排序： [1,2,3,4,5,6]， 2. 找第（n-k）小的數 n-k=4, nums[4]=5 (第2大的數） ``` ``` *時間復雜度:*`O(nlogn) - n 是數組長度。` #### 解法二 - 小頂堆（Heap）可以維護一個大小為`K`的小頂堆，堆頂是最小元素，當堆的`size > K` 的時候，刪除堆頂元素. 掃描一遍數組，最后堆頂就是第`K`大的元素。直接返回。例如： ![](https://img.kancloud.cn/cf/77/cf772edcbe871b87bbe071570c0c851d_1394x1080.jpg) *時間復雜度*：`O(n * logk) , n is array length`*空間復雜度*：`O(k)` 跟排序相比，以空間換時間。 #### 解法三 - Quick Select Quick Select 類似快排，選取pivot，把小于pivot的元素都移到pivot之前，這樣pivot所在位置就是第pivot index 小的元素。但是不需要完全給數組排序，只要找到當前pivot的位置是否是在第(n-k)小的位置，如果是，找到第k大的數直接返回。具體步驟： ``` <pre class="calibre18">``` 1. 在數組區間隨機取`pivot index = left + random[right-left]`. 2. 根據pivot 做 partition，在數組區間，把小于pivot的數都移到pivot左邊。 3. 得到pivot的位置 index，`compare(index, (n-k))`. a. index == n-k -> 找到第`k`大元素，直接返回結果。 b. index < n-k -> 說明在`index`右邊，繼續找數組區間`[index+1, right]` c. index > n-k -> 那么第`k`大數在`index`左邊，繼續查找數組區間`[left, index-1]`. 例子，【3,2,3,1,2,4,5,5,6]， k = 4 如下圖： ``` ``` ![](https://img.kancloud.cn/00/3d/003d4c733496a1c446c6112fe1af52a9_1245x861.jpg) *時間復雜度*： - 平均是：`O(n)` - 最壞的情況是：`O(n * n)` ## 關鍵點分析 1. 直接排序很簡單 2. 堆（Heap）主要是要維護一個K大小的小頂堆，掃描一遍數組，最后堆頂元素即是所求。 3. Quick Select, 關鍵是是取pivot，對數組區間做partition，比較pivot的位置，類似二分，取pivot左邊或右邊繼續遞歸查找。 ## 代碼（Java code） *解法一 - 排序* ``` <pre class="calibre18">``` class KthLargestElementSort { public int findKthlargest2(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } } ``` ``` *解法二 - Heap （PriorityQueue）* ``` <pre class="calibre18">``` class KthLargestElementHeap { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int num : nums) { pq.offer(num); if (pq.size() > k) { pq.poll(); } } return pq.poll(); } } ``` ``` *解法三 - Quick Select* ``` <pre class="calibre18">``` class KthLargestElementQuickSelect { static Random random = new Random(); public int findKthLargest3(int[] nums, int k) { int len = nums.length; return select(nums, 0, len - 1, len - k); } private int select(int[] nums, int left, int right, int k) { if (left == right) return nums[left]; // random select pivotIndex between left and right int pivotIndex = left + random.nextInt(right - left); // do partition, move smaller than pivot number into pivot left int pos = partition(nums, left, right, pivotIndex); if (pos == k) { return nums[pos]; } else if (pos > k) { return select(nums, left, pos - 1, k); } else { return select(nums, pos + 1, right, k); } } private int partition(int[] nums, int left, int right, int pivotIndex) { int pivot = nums[pivotIndex]; // move pivot to end swap(nums, right, pivotIndex); int pos = left; // move smaller num to pivot left for (int i = left; i <= right; i++) { if (nums[i] < pivot) { swap(nums, pos++, i); } } // move pivot to original place swap(nums, right, pos); return pos; } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } ``` ``` ## 參考（References） 1. [Quick Select Wiki](https://en.wikipedia.org/wiki/Quickselect)