找第k小數(shù)的分治算法描述
自然語(yǔ)言描述：
在數(shù)組中隨機(jī)選一個(gè)數(shù)作為基準(zhǔn)，把數(shù)組分成三部分：比基準(zhǔn)小的、等于基準(zhǔn)的、比基準(zhǔn)大的，計(jì)算每部分有多少個(gè)數(shù)

判斷：
如果k在"小"的部分，就在那部分繼續(xù)找第k小的數(shù)
如果k在"等"的部分，基準(zhǔn)就是答案
如果k在"大"的部分，就在那部分找第(k-小部分-等部分)小的數(shù)

偽代碼：
text
function findKthSmallest(arr, k):
pivot = 隨機(jī)選擇arr中的一個(gè)元素
small = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
large = [x for x in arr if x > pivot]

if k <= len(small):
    return findKthSmallest(small, k)
else if k <= len(small) + len(equal):
    return pivot
else:
    return findKthSmallest(large, k - len(small) - len(equal))

時(shí)間復(fù)雜度分析
最好情況：O(n)
每次都能扔掉一半數(shù)據(jù)
如：T(n) = T(n/2) + n → O(n)

最壞情況：O(n2)
每次只能減少一個(gè)元素
如：T(n) = T(n-1) + n → O(n2)

對(duì)分治法的體會(huì)
核心思想：大事化小，小事化了

優(yōu)點(diǎn)：
1、復(fù)雜問(wèn)題變簡(jiǎn)單
2、代碼容易理解和實(shí)現(xiàn)
3、有時(shí)能大幅提高效率

難點(diǎn)：
1、要找到合適的分割點(diǎn)
2、遞歸邊界容易出錯(cuò)
3、合并結(jié)果需要技巧

感悟：分治法像"團(tuán)隊(duì)協(xié)作"——把大任務(wù)拆成小任務(wù)分給不同人，最后匯總結(jié)果。這種"分而治之"的思想在編程和生活中都很實(shí)用。