多種解法破中等題
- 2019 年 10 月 5 日
- 筆記
多種解法破中等題
0.說在前面1.數組中的第K個最大元素1.0 問題1.1 降序方法1.2 遞歸快排1.3 非遞歸快排1.4 最大堆排序1.5 最小堆排序2.二叉搜索樹中第K小的元素2.0 問題2.1 遞歸中序遍歷2.2 非遞歸中序遍歷
0.說在前面
本周還差一次，今天刷兩道，分別為數組中的第k個最大元素與二叉搜索樹中第k小的元素！
1.數組中的第K個最大元素
1.0 問題
在未排序的數組中找到第 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
1.1 降序方法
【思路】
直接將數組排序即可，然後取出第k-1個元素就是結果！
【實現】
def findKthLargest(self, nums, k): if not nums: return None nums.sort(reverse=True) return nums[k-1]
【分析】
實踐複雜度為O(nlogn)，空間複雜度為O(1)
1.2 遞歸快排
【思想】
既然是尋找第k個最大元素，我們想到排序中的一些演算法，發現快排是最合適的，怎麼說呢？
快排是以樞椎privot為界限，分左邊與右邊，我們假設是降序快排，那麼樞椎左邊的元素都比樞椎值本身大，右邊的元素都比樞椎值本身小，這就引出了一個思想：當某次快排結束後，剛好這個樞椎放在了第k個位置上，那麼我們可以確定，這個元素就是第k個最大！
上面思想轉化為具體的思路為：樞椎值最後填充的位置假設為i，那麼i+1就是真實的位置，因為index從0開始，而當i+1與k相等，就是第k個最大；如果i+1小於k，那麼我們就需要從i的後面元素尋找第k個最大；如果i+1大於k，那麼我們就需要從i的前面元素尋找第k個最大!
【實現】
def findKthLargest(self, nums, k): return self.quicksort(nums,0,len(nums)-1,k) def quicksort(self,nums,low,high,k): if low>high: return privot = nums[low] i = low j = high while i<j: while i<j and nums[j]<=privot: j-=1 if i<j: nums[i]=nums[j] i+=1 while i<j and nums[i]>privot: i+=1 if i<j: nums[j]=nums[i] j-=1 nums[i] = privot # 核心思路！下面則是上面寫的思路的程式碼實現，而上面的程式碼就是快排的核心思想！ if i+1 == k: return privot if i+1 > k: return self.quicksort(nums,low, i-1,k) else: return self.quicksort(nums,i+1,high,k)
【分析】
時間複雜度為O(nlogn)，空間複雜度為O(1)
1.3 非遞歸快排
非遞歸與遞歸程式碼變動不大，主要是對於外層加了個循環條件，將內層的遞歸返回處改變上下界即可！
def findKthLargest(self, nums, k): return self.quicksort(nums,0,len(nums)-1,k) def quicksort(self,nums,low,high,k): # 這裡一定得加等於號！ while low<=high: if low>high: return privot = nums[low] i = low j = high while i<j: while i<j and nums[j]<=privot: j-=1 if i<j: nums[i]=nums[j] i+=1 while i<j and nums[i]>privot: i+=1 if i<j: nums[j]=nums[i] j-=1 nums[i] = privot if i+1 == k: return privot if i+1 > k: high=i-1 else: low=i+1
1.4 最大堆排序
【思路】
這裡使用了heapq來構建堆，調用其中的方法來實現，由於默認採用的是最小堆，那麼怎麼樣變為最大堆呢?
原數組中的數據變為負數即可！第k最大轉化為最大堆第k次pop出去的值，也就是最小堆pop出去的負數！
【實現】
def findKthLargest(self, nums, k): import heapq nums = [-i for i in nums] heapq.heapify(nums) for i in range(k): res=heapq.heappop(nums) return -res
【分析】
時間複雜度為O(n+klogn)，遍歷了一遍list，將每個數變為負數O(n)，循環k次，每次pop複雜度O(logn)，則為O(klogn)，最終實踐複雜度為O(n+logn)!
空間複雜度為O(n)。
1.5 最小堆排序
【思路】
這裡採用每次維護含k個元素的堆，我們知道最小堆堆頂為所有元素中最小的，也就是說，我每次維護的含k個元素的最小堆，堆pop出來就是我們需要的第k個最大元素！
那麼怎麼維護呢？
就是只要nums中的元素比堆頂元素大，那麼替換調這個堆頂，重新調堆，直到所有的元素循環完畢！heappush方法實現了push數據同時調整堆！
【實現】
def findKthLargest(self, nums, k): import heapq # 初始化堆,包含k個元素 # 元素值為負窮大 min_heap=[-float('inf')]*k heapq.heapify(min_heap) for i in nums: if i>min_heap[0]: heapq.heappop(min_heap) heapq.heappush(min_heap,i) return min_heap[0]
【分析】
時間複雜度為O(k+(n-k) logk)，空間複雜度為O(k)。
參考資料： https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/167837/Python-or-tm
2.二叉搜索樹中第K小的元素
2.0 問題
給定一個二叉搜索樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明： 你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。
示例 1:
輸入: root = [3,1,4,null,2], k = 1 3 / 1 4 2 輸出: 1
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / 3 6 / 2 4 / 1 輸出: 3
2.1 遞歸中序遍歷
思路就是採用中序遍歷有序性來解決，中序遍歷得到的結果是有序的，那麼取第k-1個元素就是第k個最小元素！
class Solution: def __init__(self): self.stack=[] def kthSmallest(self, root, k): self.inOrder(root) return self.stack[k-1] def inOrder(self,root): if root is None: return self.inOrder(root.left) self.stack.append(root.val) self.inOrder(root.right)
2.2 非遞歸中序遍歷
這裡思路以一個例子來模擬：
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / 3 6 / 2 4 / 1 輸出: 3
如上這個例子，首先我們來從根節點開始循環遍歷左孩子，並添加到棧中，此時棧元素有[5,3,2,1]，然後pop掉最後一個元素，得到stack=[5,3,2]，而k不為1，所以彈出來的不是第一個最小的，此時由於彈出了一個元素，那麼我們也將k減去1，也就是從剩下的元素找第K-1個最小，後面依此類推。繼續模擬：k=2，1無有節點，直接pop掉2，k減去1後為1，2無右結點，然後stack中為[5,3]，pop掉3，此時k剛好為1，那麼就是最後的結果3！
實質就是將左孩子入棧，然後判斷當前結點有無有孩子，如果有有孩子，則出棧，否則繼續添加右孩子的左孩子，重複這個操作即可！你會發現，每次pop的元素就是按照從小到大的順序pop的，所以不斷讓k減去1，每次pop掉，k減少，當k為1的時候，pop的元素就是最終解！
def kthSmallest(self, root, k): stack = [] while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if k==1: return root.val else: k-=1 root=root.right
參考資料： https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/131184/Python-3-iterative-and-recursive-solution
