本文實(shí)例講述了Python實(shí)現(xiàn)查找最小的k個數(shù)。分享給大家供大家參考，具體如下：

題目描述

輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,。

解法1

使用partition函數(shù)可以知道，使用==O(N)==的時間復(fù)雜度就可以找出第K大的數(shù)字，并且左邊的數(shù)字比這個數(shù)小，右邊的數(shù)字比這個數(shù)字大。因此可以取k為4，然后輸出前k個數(shù)字，如果需要排序的話再對結(jié)果進(jìn)行排序

# -*- coding:utf-8 -*-class Solution:  def PartitionOfK(self, numbers, start, end, k):    if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:      return    low, high = start, end    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    if low < k:      self.PartitionOfK(numbers, start + 1, end, k)    elif low > k:      self.PartitionOfK(numbers, start, end - 1, k)  def GetLeastNumbers_Solution(self, tinput, k):    # write code here    if k <= 0 or tinput == [] or k > len(tinput):      return []    self.PartitionOfK(tinput, 0, len(tinput) - 1, k)    return sorted(tinput[0:k])#測試：sol = Solution()listNum = [4,5,1,6,2,7,3,8]rel = sol.GetLeastNumbers_Solution(listNum, 4)print(rel)

運(yùn)行時間：30ms

占用內(nèi)存：5732k

解法2

解法1存在兩個問題，一個是partition把數(shù)組的順序改變了，第二是無法處理海量的數(shù)據(jù)，海量的數(shù)組全部導(dǎo)入到內(nèi)存里面做partition顯然是不合適的。因此可以找出結(jié)果中最大的數(shù)字，如果遍歷的數(shù)字比這個數(shù)字小，則替換，否則不變，可以采用堆的形式來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，達(dá)到O(logK)的復(fù)雜度，因此整體的時間復(fù)雜度為N*O(logK)

# -*- coding:utf-8 -*-class Solution:  def GetLeastNumbers_Solution(self, tinput, k):    # write code here    if tinput == [] or k <= 0 or k > len(tinput):      return []    result = []    for num in tinput:      if len(result) < k:        result.append(num)      else:        if num < max(result):          result[result.index(max(result))] = num    return sorted(result)#測試：sol = Solution()listNum = [4,5,1,6,2,7,3,8]rel = sol.GetLeastNumbers_Solution(listNum, 4)print(rel)

運(yùn)行結(jié)果同上

運(yùn)行時間：25ms

占用內(nèi)存：5724k

時間和空間占用都比解法1更優(yōu)。

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計(jì)有所幫助。