选择问题
选择问题是求集合的第\(k\)小(第\(k\)大)元素。具体可表述为“给定乱序序列，求其递减排序序列中，下标为\(k-1\)的元素”。最容易想到的是直接用\(O(nlgn)\)分治排序对整个序列排序，另一种思路是遍历\(k\)次序列，每轮都求一个最大值的下标，每轮求的时候都避开之前已求出的下标，这样代价是\(O(nk)\)，如果\(k\)是常数就是\(O(n)\)，但如果\(k\)和\(n\)同阶就是\(O(n^2)\)。
这里看一种基于快速排序的算法，快速排序每次递归都会把序列分为左右两半，右半边的任意元素都大于等于左半边的任意元素。这时如果分别记录左半边和右半边的长度，就能确定第\(k\)小元素是在左半边还是右半边。接下来就不用像快排那样分别递归左半边和右半边，只需要递归两者中的其中一个。递归前需要把\(k\)换算，转换成表示“子问题”中的第\(k’\)小元素。
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 | def selectK(arr,k): low = 0 high = len(arr) -1 return select(arr,low,high,k) def select(arr,p,r,i): if p == r: return arr[p] q = partition(arr,p,r) k = q - p + 1 if i == k: return arr[q] elif i < k: return select(arr,p,q-1,i) else: return select(arr,q+1,r,i-k) def partition(arr,p,r): x = arr[r] i = p - 1 for j in range(p,r): if arr[j] <= x: i += 1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[r] = arr[r],arr[i+1] return i+1 print(selectK([4,4,3,1,2,2,3,5,2],4)) |
最后分析时间复杂度，前面提过快排不能保证每次递归都把序列分成“差不多等长”的。这里为简化分析，假设快排每次递归可以把序列分成“差不多等长”的。这样时间复杂度就满足\(T(n)=T(\frac{n}{2}) + O(n)\)，根据算法主定理求出\(T(n)=O(n)\)。虽然这里进行了假设，但是这个算法的平均时间复杂度确实是\(O(n)\)。