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