題目描述
輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,。
這個題目完成的思路有很多，很多排序算法都可以完成既定操作，關(guān)鍵是復雜度性的考慮。以下幾種思路當是筆者拋磚引玉，如果讀者有興趣可以自己再使用其他方法一一嘗試。
思路1：利用冒泡法
臨近的數(shù)字兩兩進行比較,按照從小到大的順序進行交換,如果前面的值比后面的大，則交換順序。這樣一趟過去后,最小的數(shù)字被交換到了第一位；然后是次小的交換到了第二位，。。。，依次直到第k個數(shù)，停止交換。返回lists的前k個數(shù)（lists[0:k]，前閉后開）
思路2：使用快排中的partition思想。
①我們設定partition函數(shù)的哨兵為key=lists[left]，在partition函數(shù)中完成一輪比較的結(jié)果是，比key大的數(shù)都在其右邊，比key小的數(shù)放在其左邊。完成該輪后返回其left=right時left的值。
②我們判斷l(xiāng)eft的值是比k大還是?。?/p>
如果left的值比k大，說明上輪partition之后，lists中前l(fā)eft個小的數(shù)在左邊，其余的數(shù)在其右邊，我們還需要把尋找范圍縮小，下次找的時候只在數(shù)組前面left個數(shù)中找了。
如果left的值比k小，說明上輪partition之后，前l(fā)eft個數(shù)找的太少了，我們需要再往數(shù)組的后面找。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
# -*- coding: utf-8 -*- """ Date: Tue Sep 19 10:50:11 2017 Created by @author: xiaoguibao E-mail: [email protected] Content: 找最小的k個數(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個部分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個數(shù)實例代碼的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/u010636181/article/details/78417977
