Python找出最小的K個(gè)數(shù)實(shí)例代碼

更新時(shí)間：2018年01月04日 11:20:04 作者：明柳夢(mèng)少

這篇文章主要介紹了Python找出最小的K個(gè)數(shù)實(shí)例代碼，簡(jiǎn)單分析了實(shí)現(xiàn)思路，冒泡法和partition思想，具有一定借鑒價(jià)值,需要的朋友可以參考下

題目描述

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

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

思路1：利用冒泡法

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

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

①我們?cè)O(shè)定partition函數(shù)的哨兵為key=lists[left]，在partition函數(shù)中完成一輪比較的結(jié)果是，比key大的數(shù)都在其右邊，比key小的數(shù)放在其左邊。完成該輪后返回其left=right時(shí)left的值。

②我們判斷l(xiāng)eft的值是比k大還是?。?/p>

如果left的值比k大，說(shuō)明上輪partition之后，lists中前l(fā)eft個(gè)小的數(shù)在左邊，其余的數(shù)在其右邊，我們還需要把尋找范圍縮小，下次找的時(shí)候只在數(shù)組前面left個(gè)數(shù)中找了。

如果left的值比k小，說(shuō)明上輪partition之后，前l(fā)eft個(gè)數(shù)找的太少了，我們需要再往數(shù)組的后面找。

# -*- coding: utf-8 -*- 
""" 
Date: Tue Sep 19 10:50:11 2017 
 
Created by @author: xiaoguibao 
 
E-mail: mingliumengshao@163.com 
 
Content: 找最小的k個(gè)數(shù) 
 
""" 
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個(gè)部分function2_partion和function2 
""" 
 
def function2_partion(lists,left,right): 
  #劃分函數(shù)處理部分 
  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): 
  #劃分法主要函數(shù)部分 
  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()

總結(jié)

以上就是本文關(guān)于Python找出最小的K個(gè)數(shù)實(shí)例代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專(zhuān)題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: