Python實(shí)現(xiàn)查找數(shù)組中任意第k大的數(shù)字算法示例

發(fā)布時(shí)間：2020-09-08 20:05:13 來源：腳本之家閱讀：172 作者：hustfc 欄目：開發(fā)技術(shù)

本文實(shí)例講述了Python實(shí)現(xiàn)查找數(shù)組中任意第k大的數(shù)字算法。分享給大家供大家參考，具體如下：

模仿partion方法，當(dāng)high=low小于k的時(shí)候，在后半部分搜索，當(dāng)high=low大于k的時(shí)候，在前半部分搜索。與快排不同的是，每次都減少了一半的排序。

def partitionOfK(numbers, start, end, k):
  if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
    return None
  low = start
  high = end
  key = numbers[start]
  while low < high:
    while low < high and numbers[high] >= key:
      high -= 1
    numbers[low] = numbers[high]
    while low < high and numbers[low] <= key:
      low += 1
    numbers[high] = numbers[low]
  numbers[low] = key
  if low < k:
    return partitionOfK(numbers, start + 1, end, k)
  elif low > k:
    return partitionOfK(numbers, start, end - 1, k)
  else:
    return numbers[low]
numbers = [3,5,6,7,2,-1,9,3]
print(sorted(numbers))
print(partitionOfK(numbers, 0, len(numbers) - 1, 5))

輸出：返回了第五大排序的數(shù)字

[-1, 2, 3, 3, 5, 6, 7, 9]
6

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python列表(list)操作技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計(jì)有所幫助。

向AI問一下細(xì)節(jié)

Python實(shí)現(xiàn)查找數(shù)組中任意第k大的數(shù)字算法示例

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽