漫畫：美團面試題（TOPK：求第K個最大的元素）
- 2020 年 3 月 30 日
- 筆記
01 PART
第K個最大元素
這個題目的變形很多，比如找 "前 K 個高頻元素"、 "數據流中的第K大元素" 、"最接近原點的 K 個值" 等等等等。
第215題：在未排序的數組中找到第 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
02 PART
大頂堆
堆在演算法題目中的應用主要包括以下幾點：
- TopK 問題 （尤其是大數據處理）
- 優先隊列
- 利用堆求中位數
這種題目，從個人來講，我一般是比較偏好使用堆來做的。畢竟大小頂堆，剛好有著與本類題型契合的特性。如果對堆不太熟悉的話，可以先看下這篇文章：
那本題如何使用堆來做呢？假若我們的數組為[3,2,1,5,6,4]，k=2，我們對其構造一個小頂堆（每個結點的值均不大於其左右孩子結點的值，堆頂元素為整個堆的最小值），整個過程是這樣：
- 構造一個小頂堆，依次將元素放入堆中，並保證堆中元素為k。
- 如果當前元素小於堆頂元素，那基本就不用看了（因為我們要找的是 排序後的第 k 個最大的元素）
- 自然，如果我們遇到比堆頂元素大的元素，就把它放入到堆中。
- 重複上面的步驟：
然後根據分析，完成程式碼（今天就不手撕堆了，因為之前已經手撕過了。同時這裡給大家一個建議，如果面試的時候，遇到這種TOPK的問題，假如特別有把握，肯定得手撕數據結構，一定會加分。但是如果沒有把握，那就先用API實現，以 BugFree 為目標吧！）
//JAVA class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); for (int num : nums) { if (minQueue.size() < k || num > minQueue.peek()) { minQueue.offer(num); } if (minQueue.size() > k) { minQueue.poll(); } } return minQueue.peek(); } }
我也不知道為啥，Python永遠就是這麼牛X，樸實無華且枯燥！
//python class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k, nums)[-1]
註：python可以使用heapq.nlargest 或 heapq.nsmallest，來找出某個集合中找出最大或最小的N個元素。
//python >>> import heapq >>> nums=[1,8,2,23,7,-4,18,23,42,37,2] >>> print(heapq.nlargest(3,nums)) [42, 37, 23] >>> print(heapq.nsmallest(3,nums)) [-4, 1, 2]
鄭重申明（讀我的文章必看）：
- 本系列所有教程都不會用到複雜的語言特性，大家無須擔心沒有學過相關語法，演算法思想才是最重要的！
- 作為學術文章，雖然風格可以風趣，但嚴謹，我是認真的。本文所有程式碼均在leetcode進行過測試運行。
03 PART
快排
快速排序（Quicksort）是對冒泡排序的一種改進。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
那對於本題，我們就是使用快排的思想，選定一個基準值，把比基準值大的放在基準值的右邊，把基準值小的放在基準值的左邊。若基準值剛好位於倒數第k個數，則基準值為目標值；反之，則遞歸處理目標值所處的那一部分數組。
//go func findKthLargest(nums []int, k int) int { idx := quickSort(0, len(nums) - 1, len(nums) - k, nums) return nums[idx] } func quickSort(l, r, pos int, nums []int) int { povit_idx := partition(l, r, nums) if pos == povit_idx { return povit_idx } else if pos > povit_idx { return quickSort(povit_idx + 1, r, pos, nums) } else { return quickSort(l, povit_idx - 1, pos, nums) } } func partition(l, r int, nums []int) int { s := l povit_value := nums[l] for l < r { for ;l < r && nums[r] >= povit_value; { r-- } for ;l < r && nums[l] <= povit_value; { l++ } if l < r { nums[l] = nums[r] ^ nums[l] nums[r] = nums[l] ^ nums[r] nums[l] = nums[r] ^ nums[l] } } nums[s] = nums[l] nums[l] = povit_value return l }
整個快排的核心，其實就partition。partition 有 單向掃描，雙向掃描 等多種寫法。上面的程式碼，大家可以參考參考，看不懂也沒關係，我後面是會單獨安排一個快排的系列篇來進行講解的，到時候一堆圖解砸進來，保准你看的醍醐灌頂！
