[剑指Offer]最小的K个数

题目描述

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

解题思路

略。

代码

Python(2.7.3)

Tim排序法

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

运行时间：23ms
占用内存：5624k

快速排序法

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput):
            return []
        return self.quick_sort(tinput)[:k]
    
    def quick_sort(self, array):
        if len(array) < 2:
            return array
        pivot = array[0]
        left, right = [], []
        for i in array[1:]:
            if i <= pivot:
                left.append(i)
            else:
                right.append(i)
        left = self.quick_sort(left)
        right = self.quick_sort(right)
        return left + [pivot] + right

运行时间：24ms
占用内存：5732k