心路历程:
这道题本质上是排序不完全的过程,而且这道题有bug,直接用python的排序算法其实就能AC。
可以按照快排排到找到k-1个large元素的思维去做,不过这道题需要考虑空间复杂度,所以需要用指针快排。
其实也可以考虑用K次的冒泡排序。
注意的点:
1、思考递归函数需要只想当前层的处理逻辑,不要多深入往下一层去思考,否则容易乱
2、用快排来做这道题的递归函数不需要边界条件判断
98%AC:快排(内存超了)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quick(alist): # 将alist分为两部分查找
nonlocal k
target = alist[0]
small, large = [], [] # 这块比较费内存
for i in range(1, len(alist)):
if alist[i] < target: small.append(alist[i])
else: large.append(alist[i])
if len(large) == k - 1: return target
elif len(large) > k - 1:
return quick(large)
else:
k -= len(large) + 1
return quick(small)
return quick(nums)