欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python查找第k小元素代碼分享

 更新時間:2013年12月18日 09:48:29   作者:  
這篇文章分享了python查找第k小的元素程序代碼,大家參考使用吧

復(fù)制代碼 代碼如下:

# -*- coding: utf-8 -*-

from random import randint
from math import ceil, floor

def _partition(A, l, r, i):
    """以A[i]為主元劃分?jǐn)?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 # 索引標(biāo)記
    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):
    """隨機(jī)劃分主元"""
    return randint(l, r) # A[l..r]隨機(jī)取一個

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): 主元選取方法,默認(rèn)隨機(jī)方式
    """
    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):
    """默認(rèn)隨機(jī)劃分主元方式,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))

相關(guān)文章

  • 壓縮包密碼破解示例分享(類似典破解)

    壓縮包密碼破解示例分享(類似典破解)

    有一個壓縮包密碼忘了,寫了一個小腳本實(shí)現(xiàn)一個解密的功能,輸入自己常用密碼中的單詞后,腳本將這些密碼組合嘗試解壓壓縮包
    2014-01-01
  • 對pandas里的loc并列條件索引的實(shí)例講解

    對pandas里的loc并列條件索引的實(shí)例講解

    今天小編就為大家分享一篇對pandas里的loc并列條件索引的實(shí)例講解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-11-11
  • Python代碼調(diào)試的幾種方法總結(jié)

    Python代碼調(diào)試的幾種方法總結(jié)

    這篇文章主要介紹了Python代碼調(diào)試的幾種方法總結(jié),本文來自于IBM官方網(wǎng)站技術(shù)文檔,需要的朋友可以參考下
    2015-04-04
  • Python利用PyPDF2庫獲取PDF文件總頁碼實(shí)例

    Python利用PyPDF2庫獲取PDF文件總頁碼實(shí)例

    這篇文章主要介紹了Python利用PyPDF2庫獲取PDF文件總頁碼實(shí)例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-04-04
  • 使用python如何刪除同一文件夾下相似的圖片

    使用python如何刪除同一文件夾下相似的圖片

    這篇文章主要給大家介紹了關(guān)于利用python如何刪除同一文件夾下相似的圖片的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-05-05
  • Python輕量級Web框架之Flask用法詳解

    Python輕量級Web框架之Flask用法詳解

    Flask是一個用Python編寫的輕量級Web應(yīng)用框架,由于其“微”性質(zhì),Flask在提供核心服務(wù)的同時,仍然提供了許多擴(kuò)展的可能性,在這篇文章中,我們將從最基礎(chǔ)開始,學(xué)習(xí)如何使用Flask構(gòu)建一個Web應(yīng)用,需要的朋友可以參考下
    2023-08-08
  • Python編程基礎(chǔ)之輸入與輸出

    Python編程基礎(chǔ)之輸入與輸出

    這篇文章主要為大家介紹了Python輸入與輸出,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-12-12
  • Python優(yōu)雅實(shí)現(xiàn)二分查找的示例詳解

    Python優(yōu)雅實(shí)現(xiàn)二分查找的示例詳解

    二分查找是一種高效的搜索算法,用于在有序數(shù)組中查找特定元素,本文將介紹二分查找的基本原理,并通過Python代碼進(jìn)行詳細(xì)講解,需要的可以參考一下
    2023-07-07
  • python opencv實(shí)現(xiàn)任意角度的透視變換實(shí)例代碼

    python opencv實(shí)現(xiàn)任意角度的透視變換實(shí)例代碼

    這篇文章主要介紹了python opencv實(shí)現(xiàn)任意角度的透視變換實(shí)例代碼,具有一定借鑒價值,需要的朋友可以參考下
    2018-01-01
  • 回歸預(yù)測分析python數(shù)據(jù)化運(yùn)營線性回歸總結(jié)

    回歸預(yù)測分析python數(shù)據(jù)化運(yùn)營線性回歸總結(jié)

    本文主要介紹了python數(shù)據(jù)化運(yùn)營中的線性回歸一般應(yīng)用場景,常用方法,回歸實(shí)現(xiàn),回歸評估指標(biāo),效果可視化等,并采用了回歸預(yù)測分析的數(shù)據(jù)預(yù)測方法
    2021-08-08

最新評論