题目描述如下:

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

Solutions

第一种比较粗暴的解法就是排序然后找出 K 个不同的数:

# -*- coding:utf-8 -*-
class Solution:
    def partition(self, arr, low, high):
        pivot = arr[high]
        i = low
        for j in xrange(low, high):
            if arr[j] <= pivot:
                arr[j], arr[i] = arr[i], arr[j]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]
        return i
    def quick_sort(self, arr, low=0, high=None):
        if high is None:
            high = len(arr) - 1
             
        def _quicksort(arr, low, high):
            if low >= high:
                return
            pivot = self.partition(arr, low, high)
            _quicksort(arr, low, pivot-1)
            _quicksort(arr, pivot+1, high)
        return _quicksort(arr, low, high)
    
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if tinput == [] or not tinput:
            return []
        if k > len(tinput) or k == 0:
            return []
        self.quick_sort(tinput)
        res = []
        pre = tinput[0]
        res.append(pre)
        for num in tinput:
            if num != pre:
                res.append(num)
                pre = num
            if len(res) == k:
                break
        return res

第二种解法就是利用 Partition 方法,划分数据到 pivot 第 k-1 位置左右两边:

# -*- coding:utf-8 -*-
class Solution:
    def partition(self, arr, low, high):
        pivot = arr[high]
        i = low
        for j in xrange(low, high):
            if arr[j] <= pivot:
                arr[j], arr[i] = arr[i], arr[j]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]
        return i
    def quick_sort(self, arr, low=0, high=None):
        if high is None:
            high = len(arr) - 1
             
        def _quicksort(arr, low, high):
            if low >= high:
                return
            pivot = self.partition(arr, low, high)
            _quicksort(arr, low, pivot-1)
            _quicksort(arr, pivot+1, high)
        return _quicksort(arr, low, high)
    
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if tinput == [] or not tinput:
            return []
        if k > len(tinput) or k == 0:
            return []
        low = 0
        high = len(tinput) - 1
        idx = self.partition(tinput, low, high)
        while idx != k -1:
            if idx > k - 1:
                high = idx - 1
                idx = self.partition(tinput, low, high)
            else:
                low = idx + 1
                idx = self.partition(tinput, low, high)
        res = tinput[:k]
        self.quick_sort(res)
        return res

第三种方法就是使用最大堆了,这个可以用在海量数据的处理上:

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        import heapq
        if k > len(tinput):
            return []
        return heapq.nsmallest(k, tinput)

References

  1. 030. 最小的k个数