溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
題目描述
輸入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個數實例代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
