多种解法破中等题
- 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
