題目描述

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

這個題目完成的思路有很多，很多排序算法都可以完成既定操作，關鍵是復雜度性的考慮。以下幾種思路當是筆者拋磚引玉，如果讀者有興趣可以自己再使用其他方法一一嘗試。

思路1：利用冒泡法

臨近的數字兩兩進行比較,按照從小到大的順序進行交換,如果前面的值比后面的大，則交換順序。這樣一趟過去后,最小的數字被交換到了第一位；然后是次小的交換到了第二位，。。。，依次直到第k個數，停止交換。返回lists的前k個數（lists[0:k]，前閉后開）

思路2：使用快排中的partition思想。

①我們設定partition函數的哨兵為key=lists[left]，在partition函數中完成一輪比較的結果是，比key大的數都在其右邊，比key小的數放在其左邊。完成該輪后返回其left=right時left的值。

②我們判斷left的值是比k大還是小：

如果left的值比k大，說明上輪partition之后，lists中前left個小的數在左邊，其余的數在其右邊，我們還需要把尋找范圍縮小，下次找的時候只在數組前面left個數中找了。

如果left的值比k小，說明上輪partition之后，前left個數找的太少了，我們需要再往數組的后面找。

# -*- coding: utf-8 -*- """ Date: Tue Sep 19 10:50:11 2017  Created by @author: xiaoguibao  E-mail: mingliumengshao@163.com  Content: 找最小的k個數  """ def function1(lists,k): #  冒泡法   length = len(lists)   for i in range(k):     for j in range(i+1,length):       if lists[i] > lists[j]:         lists[j],lists[i] = lists[i],lists[j]   return lists[0:k]  """ 思路2 包括2個部分function2_partion和function2 """  def function2_partion(lists,left,right):   #劃分函數處理部分   key = lists[left]   while left < right:     while left < right and lists[right] >= key:       right -= 1     lists[left] = lists[right]     while left < right and lists[left] <= key:       left += 1     lists[right] = lists[left]   lists[right] = key   return left def function2(lists,k):   #劃分法主要函數部分   length = len(lists)   left = 0   right = length - 1   index = function2_partion(lists,left,right)   while k!=index:     if index > k-1:       right = index-1     else:       left = index+1     index = function2_partion(lists,left,right)    return lists[0:k]  def main():   lists = [1,1,6,4,11,9,2,10,3] #  print "思路一(冒泡法):",function1(lists,8)   print "思路二(劃分法):",function2(lists,8) if __name__=="__main__":   main() 

總結

以上就是本文關于Python找出最小的K個數實例代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！