首先一般考慮“萬能的”暴力窮舉（遞歸、回溯）。但因為窮舉時間復雜度通常過高，所以需要考慮更好的方法，如分治法（通過分而治之，然后歸并），以及空間換時間（如活用哈希表）。

此外，選擇合適的數(shù)據(jù)結(jié)構(gòu)可以顯著提升效率，如尋找最小的k個數(shù)中，用堆代替數(shù)組。

再有，如果題目允許排序，則可以考慮排序。比如，尋找和為定值的兩個數(shù)中，先排序，然后用前后兩個指針往中間掃。而如果如果已經(jīng)排好序了（如楊氏矩陣查找中），則想想有無必要二分。但是，如果題目不允許排序呢？這個時候，我們可以考慮不改變數(shù)列順序的貪心算法（如最小生成樹Prim、Kruskal及最短路dijkstra），或動態(tài)規(guī)劃（如 01背包問題，每一步都在決策）。

2.1 尋找最小的k個數(shù)：解法1， 解法4

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。

步驟為：

從數(shù)列中挑出一個元素，稱為"基準"（pivot），

重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

import random import timeit ? def quickSort(numbers): if len(numbers) <= 1: return numbers ? pivot = random.choice(numbers) less = [i for i in numbers if i < pivot] equal = [i for i in numbers if i == pivot] greater = [i for i in numbers if i > pivot] return quickSort(less) + equal + quickSort(greater) ? def quickSelect(numbers, k): pivot = random.choice(numbers) less = [i for i in numbers if i < pivot] equal = [i for i in numbers if i == pivot] greater = [i for i in numbers if i > pivot] ? if k <= len(less): return quickSelect(less, k) elif k <= len(less) + len(equal): return less + equal else: return less + equal + quickSelect(greater, k - len(less) - len(equal)) ? def main(): k = 3 numbers = [18, 27, 9, 65, 33] ? tmpNumbers = quickSort(numbers) print tmpNumbers[:k] ? tmpNumbers = quickSelect(numbers, k) print tmpNumbers ? if __name__ == '__main__': main()

轉(zhuǎn)載于:https://blog.51cto.com/ctoxiongping/1614957

總結(jié)

以上是生活随笔為你收集整理的python代码 程序员编程艺术 2.1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。