文章目录

题目描述分析解题思路一：排序思想解题思路二：快排思想解题思路三：堆排思想 代码解题思路一：排序思想解题思路二：快排思想解题思路三：堆排思想

题目描述

输入n个整数，找出其中最小的K个数。例如输入 4,5,1,6,2,7,3,8 这8个数字，则最小的4个数字是 1,2,3,4 。

分析

解题思路一：排序思想

思路： 按照升序排序，然后取前K个数，就是我们最终想要的到的结果，现在较好一点的排序方法时间复杂度是NlogN,我们还有更快的实现方法吗？

解题思路二：快排思想

思路：根据一次快排(Partition)的想法，可知一次随机快速排序可以确定一个有序的位置，这个位置的左边都小于这个数，右边都大于这个数，我们如果能找到随机快速排序确定的位置等于k-1的那个位置，那么0~k-1个数就是我们要找的数。怎么能找到那个位置： - 如果Partition确定的位置小于K-1，说明k-1这个位置在它的右边，我们继续在右边进行查找。 - 如果Partition确定的位置大于K-1，说明k-1这个位置在它的左边，我们继续在左边进行查找。

缺点： 时间复杂度虽然是O(n)，但是找出来的最小的K个数却不是排序过的。而且这种方法有个限制，就是必须修改给的数组。

解题思路三：堆排思想

适用： 处理海量数据在线数据。

思路：是建一个K个数的大顶堆，每次拿一个数和堆顶元素比较，如果这个数比堆顶元素大，则必然不是最小的K个数，如果这个数比堆顶元素小，则与堆顶元素交换，然后在向下调整一次建成新的大堆，然后遍历所有的数，直到最小的K个数都进堆里。

最大的K个数---- 建小顶堆最小的K个数----建大顶堆

优点：海量数据不占内存；实时判别新产生的数据；时间复杂度O(nlogn)。

代码

解题思路一：排序思想

# -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if tinput==None or tinput==[] or k<0 or k>len(tinput): return [] tinput.sort() return tinput[:k]

解题思路二：快排思想

# -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): n = len(tinput) if k <= 0 or k > n: return list() start = 0 end = n - 1 mid = self.partition(tinput, start, end) while k - 1 != mid: if k - 1 > mid: start = mid + 1 mid = self.partition(tinput, start, end) elif k - 1 < mid: end = mid - 1 mid = self.partition(tinput, start, end) res = tinput[:mid+1] # res.sort() return res def partition(self, numbers, low, high): key = numbers[low] while low < high: while low < high and numbers[high] >= key: high -= 1 numbers[low] = numbers[high] while low < high and numbers[low] <= key: low += 1 numbers[high] = numbers[low] numbers[low] = key return low

解题思路三：堆排思想

# -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if k > len(tinput) or k == 0: return [] self.arr = [0] for one in tinput: self.arr.append(one) self.heap_sort(self.arr, k) return [_ for _ in reversed(self.arr[-k:])] def sift(self, begin, n): i = begin j = 2*i tmp = self.arr[i] while j <= n: if j < n and self.arr[j] > self.arr[j+1]: j += 1 # 右孩子小 if tmp > self.arr[j]: self.arr[i] = self.arr[j] i = j j = 2*i else: break self.arr[i] = tmp pass def heap_sort(self, data, k): n = len(data) - 1 for i in range(int(n/2), 0, -1): # 初始化构建小顶堆 -- 得到的结果是从小到大 self.sift(i, n) # 最小3个数 for i in range(n, n-k, -1): self.arr[1], self.arr[i] = self.arr[i], self.arr[1] self.sift(1, i-1) pass