题解 | #最小的K个数#
最小的K个数
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
1.堆排序：k维大顶堆，不断推出大的，剩下的k维大顶堆就是最小的k个数。
时间复杂度：n + nlogk
class Solution: # 堆排序方法 def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]: # # 递归法，调整大顶堆 # def recurheapAdjust(li, s, m): # j = 2 * s + 1 # if j >= m: # return # if j < m - 1 and li[j] < li[j + 1]: # j = j + 1 # if li[s] < li[j]: # li[s], li[j] = li[j], li[s] # recurheapAdjust(li, j, m) # 循环法，调整大顶堆 def loopheapAdjust(li, s, m): j = 2 * s + 1 while j < m: if j < m - 1 and li[j] < li[j + 1]: j = j + 1 if li[s] >= li[j]: break li[s], li[j] = li[j], li[s] s = j j = 2 * s + 1 # 堆排序，不断把最大的弹出，剩下的最大堆就是最小的k个 def HeapSort(li, k): n = len(li) hp = li[:k] for i in range(k // 2 - 1, -1, -1): loopheapAdjust(hp, i, k) for i in range(k, n): if hp[0] > li[i]: hp[0] = li[i] loopheapAdjust(hp, 0, k) return hp return None if not k else HeapSort(input.copy(), k)2.不完全堆排序：n维小顶堆，但只进行k次，数组的后k个数就是k个最小的，毕竟题目不要求顺序。
时间复杂度：n + klogn。这比方法1的 n + nlogk 还小
class Solution: # 堆排序方法 def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]: # # 递归法，调整小顶堆 # def recurheapAdjust(li, s, m): # j = 2 * s + 1 # if j >= m: # return # if j < m - 1 and li[j] > li[j + 1]: # j = j + 1 # if li[s] > li[j]: # li[s], li[j] = li[j], li[s] # recurheapAdjust(li, j, m) # 循环法，调整小顶堆 def loopheapAdjust(li, s, m): j = 2 * s + 1 while j < m: if j < m - 1 and li[j] > li[j + 1]: j = j + 1 if li[s] <= li[j]: break li[s], li[j] = li[j], li[s] s = j j = 2 * s + 1 # 堆排序，本题只需k个最小 def HeapSort(li, k): n = len(li) for i in range(n // 2 - 1, -1, -1): loopheapAdjust(li, i, n) for i in range(n - 1, n - 1 - k, -1): li[0], li[i] = li[i], li[0] loopheapAdjust(li, 0, i) return li[-k:] return None if not k else HeapSort(input.copy(), k)3.快速排序
时间复杂度nlogn
class Solution: # 快速排序方法 def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]: def quick_sort(arr, left, right): # 终止条件 if left >= right: return # 以left为基准，不断互换，使得“左边”小于基准，“右边大于基准”。 # 过程中基准是在left处不移动的，最后把基准值移到中间即可 i, j = left, right while i < j: while i < j and arr[j] >= arr[left]: j -= 1 while i < j and arr[i] <= arr[left]: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[left], arr[i] = arr[i], arr[left] # 递归左右子数组 quick_sort(arr, left, i - 1) quick_sort(arr, i + 1, right) quick_sort(input, 0, len(input) - 1) return input[:k]4.不完全快速排序：因为基准的左边是小于基准的，所以只需基准恰好 = k，则左边的k个数就是最小的k个数，毕竟题目不要求顺序。
时间复杂度n，快速排序两头都要排，所以logn次都是n。这里的不完全快速排序，两头选一头即可，平均来看就是logn次，但每次都减半：n+n/2+n/4+... = 2*N=O(n)
class Solution: # 不完全快速排序方法 def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]: if k >= len(input): return input def quick_sort(arr, left, right): if left >= right: return i, j = left, right while i < j: while i < j and arr[j] >= arr[left]: j -= 1 while i < j and arr[i] <= arr[left]: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[left], arr[i] = arr[i], arr[left] # 递归左右子数组 if i > k: quick_sort(arr, left, i - 1) if i < k: quick_sort(arr, i + 1, right) return arr[:k] return quick_sort(input, 0, len(input) - 1)
