Python實現(xiàn)查找最小的k個數示例【兩種解法】

更新時間：2019年01月08日 08:36:23 作者：hustfc

這篇文章主要介紹了Python實現(xiàn)查找最小的k個數,結合實例形式對比分析了Python常見的兩種列表排序、查找相關操作技巧,需要的朋友可以參考下

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

題目描述

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

解法1

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

# -*- 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)

運行時間：30ms

占用內存：5732k

解法2

解法1存在兩個問題，一個是partition把數組的順序改變了，第二是無法處理海量的數據，海量的數組全部導入到內存里面做partition顯然是不合適的。因此可以找出結果中最大的數字，如果遍歷的數字比這個數字小，則替換，否則不變，可以采用堆的形式來實現(xiàn)數據結構，達到O(logK)的復雜度，因此整體的時間復雜度為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)

運行結果同上

運行時間：25ms

占用內存：5724k

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

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數學運算技巧總結》、《Python數據結構與算法教程》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。

您可能感興趣的文章: