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

員工經(jīng)過長期磨合與沉淀，具備了協(xié)作精神，得以通過團隊的力量開發(fā)出優(yōu)質(zhì)的產(chǎn)品。創(chuàng)新互聯(lián)堅持“專注、創(chuàng)新、易用”的產(chǎn)品理念，因為“專注所以專業(yè)、創(chuàng)新互聯(lián)網(wǎng)站所以易用所以簡單”。公司專注于為企業(yè)提供成都網(wǎng)站設計、網(wǎng)站制作、微信公眾號開發(fā)、電商網(wǎng)站開發(fā)，微信小程序，軟件按需設計等一站式互聯(lián)網(wǎng)企業(yè)服務。

題目描述

輸入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)==的時間復雜度就可以找出第K大的數(shù)字，并且左邊的數(shù)字比這個數(shù)小，右邊的數(shù)字比這個數(shù)字大。因此可以取k為4，然后輸出前k個數(shù)字，如果需要排序的話再對結果進行排序

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

本文題目：Python實現(xiàn)查找最小的k個數(shù)示例【兩種解法】-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://weahome.cn/article/djpoci.html