面試中常會(huì)被問到的一個(gè)經(jīng)典問題就是給定一個(gè)無序的數(shù)（N個(gè)）嘲恍，尋找其中最大（最形） 的K個(gè)（K<N）。
思路一：對(duì)整個(gè)數(shù)據(jù)進(jìn)行排序愈诚，然后選出前K個(gè)她按，可以選擇快速排序、堆排序和歸并排序炕柔，其時(shí)間復(fù)雜度都可以達(dá)到O(NlogN)
思路二：不進(jìn)行全排列酌泰，只對(duì)最大的K個(gè)排列。如利用冒泡法匕累，每次冒泡取出最大的陵刹，進(jìn)行K次，即可求得TopK.時(shí)間復(fù)雜度是O(n*k), 示例：
def bubble_sort(L, k):
if k >= len(L):
pass
for i in range(k):
# 設(shè)置一個(gè)flag欢嘿，如果某一個(gè)循環(huán)沒有交換衰琐，則整個(gè)有序，停止整個(gè)循環(huán)
flag = True
for j in range(len(L) - i - 1):
if L[j] > L[j+1]:
flag = False
L[j], L[j+1] = L[j+1], L[j]
if flag:
break
return L[len(L)-k:]
L = [4, 7, 8, 11, 3, 2]
bubble_sort(L, 2)
# [8, 11]
思路三：利用數(shù)據(jù)池思想炼蹦，首先 維護(hù)一個(gè)大小為K的數(shù)據(jù)池羡宙，將前K個(gè)數(shù)放進(jìn)去，然后將原數(shù)據(jù)中剩余的N-K個(gè)數(shù)掐隐，依次與數(shù)據(jù)池中的數(shù)據(jù)做比較狗热，遇到比當(dāng)前數(shù)小的，則替換虑省。此時(shí)的算法時(shí)間復(fù)雜度為O（N*K）
思路四：由于思路二中匿刮，與數(shù)據(jù)池中數(shù)據(jù)做比較時(shí)，是順序比較探颈，此處可以優(yōu)化熟丸。如假設(shè)數(shù)據(jù)池中的K個(gè)數(shù)據(jù)是有序的，則比較時(shí)可以借助二分的思想提高效率膝擂，但對(duì)前K個(gè)排序需要O(KlogK)虑啤。更進(jìn)一步，比較的核心是當(dāng)前數(shù)據(jù)池中的數(shù)據(jù)是否有需要替換的架馋，即知道當(dāng)前數(shù)據(jù)池中的最小值即可狞山，而不需要完全排序。
按照這個(gè)思路叉寂，我們維護(hù)一個(gè)大小為K的小根堆萍启，然后依次將原始數(shù)據(jù)中的數(shù)與根對(duì)比，如比根元素大，則進(jìn)行替換并進(jìn)行堆調(diào)整勘纯，即保證數(shù)據(jù)池中數(shù)據(jù)是當(dāng)前的TopK局服，又保證根節(jié)點(diǎn)是最小值。此時(shí)該算法的時(shí)間負(fù)責(zé)度為O(NlogK)
import heapq
def TopK(L, k):
"""
利用大小為K的堆作為數(shù)據(jù)池驳遵，依次對(duì)比
tips：headp實(shí)現(xiàn)的是小頂堆淫奔，無法傳入比較函數(shù)，若要實(shí)現(xiàn)最小的TopK堤结，可以傳入-item,pop后取負(fù)還原
"""
r = []
for j in range(len(L)):
if j < k:
heapq.heappush(r, L[j])
else:
if r[0] < L[j]:
heapq.heapreplace(r, L[j])
return r
# test
L = [9,7,1,2,6,3]
TopK(L,2)
# [7, 9]
思路五：利用快速排序的分劃函數(shù)找到分劃位置K唆迁，即第K大的數(shù)，則其左側(cè)即為所求竞穷√圃穑快速排序的核心是
i = partition(L, low, high)
其中默認(rèn)第一個(gè)元素f是比較基數(shù)，然后將數(shù)組L[low, high] 劃分為都比f大的左部分和比f小的右部分瘾带，中間位置是基數(shù)f鼠哥。每次劃分后，如果i > k, 則說明前K個(gè)數(shù)在L[:i]內(nèi)看政，進(jìn)一步在L[:i]中尋找朴恳；如果i < k,則前i個(gè)數(shù)即是最大k個(gè)數(shù)中的i個(gè)，繼續(xù)在剩余的L[i:]中尋找第 k - i 大的數(shù)帽衙；如果 i==k ,則說明此時(shí)前i個(gè)即為最大的k個(gè)菜皂。
def partition(L, left, right):
"""
將L[left:right]進(jìn)行一次快速排序的partition，返回分割點(diǎn)
:param L: 數(shù)據(jù)List
:param left: 排序起始位置
:param right: 排序終止位置
:return: 分割點(diǎn)
"""
if left < right:
key = L[left]
low = left
high = right
while low < high:
while low < high and L[high] <= key:
high = high - 1
L[low] = L[high]
while low < high and L[low] >= key:
low = low + 1
L[high] = L[low]
L[low] = key
print(L)
return low
def topK(K, L):
if K > len(L):
pass
l = 0
r = len(L) - 1
j = partition(L, l, r)
print(j)
while j != K:
if j < K:
l = j + 1
else:
r = j
j = partition(L, l, r)
return L[:K]
# test
L = [4,3,1,2,5]
right=len(L)-1
left=0
topK(2,L)
#[5, 4]
