中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Python找出最小的K個數實例代碼

發布時間:2020-10-07 10:50:16 來源:腳本之家 閱讀:197 作者:明柳夢少 欄目:開發技術

題目描述

輸入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個數實例代碼的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

西城区| 甘肃省| 贵溪市| 延津县| 康乐县| 田东县| 济阳县| 黔西县| 屯昌县| 聊城市| 辽阳市| 隆德县| 营山县| 平罗县| 鹤山市| 同德县| 巴楚县| 荆门市| 岚皋县| 永济市| 芦溪县| 玉溪市| 名山县| 乌什县| 石河子市| 克什克腾旗| 平邑县| 荥阳市| 乐平市| 青田县| 明光市| 安泽县| 望谟县| 广昌县| 乌审旗| 隆昌县| 凤阳县| 临夏县| 浦北县| 尤溪县| 唐海县|