python查找第k小元素代碼分享
# -*- coding: utf-8 -*-
from random import randint
from math import ceil, floor
def _partition(A, l, r, i):
"""以A[i]為主元劃分數(shù)組A[l..r],使得:
A[l..m-1] <= A[m] < A[m+1..r]
"""
A[i], A[r] = A[r], A[i] # i交換到末位r,作為主元
pivot = A[r] # 主元
m = l # 索引標記
for n in xrange(l, r): # l..r-1
if A[n] <= pivot:
A[m], A[n] = A[n], A[m] # 交換
m += 1 # 后移
A[m], A[r] = A[r], A[m] # 主元到m位
return m
def _rand(A, l, r):
"""隨機劃分主元"""
return randint(l, r) # A[l..r]隨機取一個
def _select(A, l, r, k, pivot_selector = _rand):
"""利用快排,得A[l..r]中第k小的數(shù),k in [l+1,r+1]:
其尾遞歸方式,偽碼如下:
SELECT(A, l, r, k)
1 while true:
2 i ← ? // 劃分主元位置
3 m ← PARTITION(A, l, r, i) // 數(shù)組劃分
4 n ← m - l + 1 // A[l..m]元素個數(shù)
5 if k = n // 檢查A[m]是否是第k小的元素
6 then return A[m]
7 elseif k < n // 左劃分區(qū)
8 r = m - 1
9 else // 右劃分區(qū)
10 k = k - n
11 l = m + 1
Args:
pivot_selector(Function): 主元選取方法,默認隨機方式
"""
if not A:
return None
if l == r:
return A[l]
while True:
i = pivot_selector(A, l, r)
m = _partition(A, l, r, i)
n = m - l + 1
if k == n:
return A[m]
elif k < n:
r = m - 1
else:
k = k - n
l = m + 1
def rand_select(A, k):
"""默認隨機劃分主元方式,k in [1, len(A)]
E[T(n)] = O(n)
"""
return _select(A, 0, len(A) - 1, k);
def _median(A, l, r):
"""對A[l..r]插入排序(原地)后選取其中位數(shù)位置"""
for j in xrange(l, r + 1):
k = A[j]
i = j
while i > l and A[i-1] > k:
A[i] = A[i-1]
i -= 1
A[i] = k
return l + int((r - l) * 0.5) # 下中位數(shù)
def _medianOfMedians(A, l, r):
"""中位數(shù)的中位數(shù)方式:
1. 劃分為floor(n/5)個5元組,剩下(n%5)組成最后一組。
2. 找出ceil(n/5)個組各自的中位數(shù)。先對每組插入排序,再從中選出中位數(shù)。
3. 對第2步中找出的ceil(n/5)個中位數(shù)重復(fù)上述操作,直到僅有一個中位數(shù)。
"""
if l == r:
return l
n = r - l + 1 # 元素個數(shù)
m = int(ceil(n / 5.0)) # 劃分組數(shù),每組5個元素
for i in xrange(m):
# 每組起始位和結(jié)束位
sub_l = l + i * 5
sub_r = sub_l + 4
if sub_r > r:
sub_r = r
# 對每組元素插入排序后,選取中位數(shù)
sub_m = _median(A, sub_l, sub_r) # 中位數(shù)索引
# 交換中位數(shù)到前幾位
j = l + i
A[j], A[sub_m] = A[sub_m], A[j]
return _medianOfMedians(A, l, l + m - 1) # 中位數(shù)的中位數(shù)
def bfprt_select(A, k):
"""中位數(shù)的中位數(shù)方式(BFPRT算法)
T(n) = O(n)
"""
return _select(A, 0, len(A) - 1, k, _medianOfMedians);
def _median3(A, l, r):
"""三數(shù)中位數(shù)方式,取l,r,(l+r)/2三數(shù)中位數(shù)"""
c = (l + r) / 2
keys = [l, c, r]
i = _median(keys, 0, 2)
return keys[i]
def median_select(A, k):
"""三數(shù)中位數(shù)方式,以消除最壞情況"""
return _select(A, 0, len(A) - 1, k, _median3);
if __name__ == '__main__':
import random, time
from copy import copy
print('preparing data...')
n = 1000000
nums = range(n)
random.shuffle(nums)
print('ready go!')
def timeit(fnc, *args, **kargs):
print('%s starts processing' % fnc.__name__)
begtime = time.clock()
retval = fnc(*args, **kargs)
endtime = time.clock()
print('%s takes time : %f' % (fnc.__name__, endtime - begtime))
return retval
test_methods = [rand_select, bfprt_select, median_select]
k = random.randrange(n) + 1
dashes = '---' * 10
for test in test_methods:
print(dashes)
nums_new = copy(nums)
result = timeit(test, nums_new, k)
print('the %dth smallest element: %d' % (k, result))
- Python cookbook(數(shù)據(jù)結(jié)構(gòu)與算法)保存最后N個元素的方法
- Python cookbook(數(shù)據(jù)結(jié)構(gòu)與算法)從任意長度的可迭代對象中分解元素操作示例
- Python cookbook(數(shù)據(jù)結(jié)構(gòu)與算法)將序列分解為單獨變量的方法
- 利用Python找出序列中出現(xiàn)最多的元素示例代碼
- Python找出list中最常出現(xiàn)元素的方法
- Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之鏈表詳解
- Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
- Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊列詳解
- Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之基本搜索詳解
- Python數(shù)據(jù)結(jié)構(gòu)與算法之圖結(jié)構(gòu)(Graph)實例分析
- Python cookbook(數(shù)據(jù)結(jié)構(gòu)與算法)找到最大或最小的N個元素實現(xiàn)方法示例
相關(guān)文章
Python優(yōu)雅實現(xiàn)二分查找的示例詳解
二分查找是一種高效的搜索算法,用于在有序數(shù)組中查找特定元素,本文將介紹二分查找的基本原理,并通過Python代碼進行詳細講解,需要的可以參考一下2023-07-07python opencv實現(xiàn)任意角度的透視變換實例代碼
這篇文章主要介紹了python opencv實現(xiàn)任意角度的透視變換實例代碼,具有一定借鑒價值,需要的朋友可以參考下2018-01-01回歸預(yù)測分析python數(shù)據(jù)化運營線性回歸總結(jié)
本文主要介紹了python數(shù)據(jù)化運營中的線性回歸一般應(yīng)用場景,常用方法,回歸實現(xiàn),回歸評估指標,效果可視化等,并采用了回歸預(yù)測分析的數(shù)據(jù)預(yù)測方法2021-08-08