よくある質問:無秩序配列のk番目に大きい数(python)

考え方1:暴力解法
配列を並べ替えてk番目の位置を見つけます

sorted(nums)[-k]

アルゴリズムの時間的複雑度はO(N log N),空間的複雑度はO(1)である.
考え方2:速排思想を利用する
(https://blog.csdn.net/wenqiwenqi123/article/details/81669899)クイックソートは、1つの要素を正しい位置に交換するたびに、左の要素を大きくし、右の要素を小さくします.このアルゴリズムは毎回ピボットを選択し、ソートした後、ピボットの位置を表示します.その位置がKより大きい場合、前のサブシーケンスのK番目の大きな要素が要求されることを示す.逆に、Kより小さい場合は、後のシーケンスのK番目〜前のシーケンスの長さの要素が要求されることを示す.
このようにして、この問題を速い考えで解決できる問題に変えた.高速ソートの場合、アルゴリズムの複雑さはO(N*logN)である.このアルゴリズムのアルゴリズム複雑度はO(N)である.どうしてですか.
実はこの場所のアルゴリズムの複雑さの分析はとても面白いです.1回目の交換はアルゴリズム複雑度がO(N)であり,次のプロセスは高速ソートとは異なり,高速ソートは両側のデータを処理し続け,再結合し,合成操作のアルゴリズム複雑度がO(1)であるため,総アルゴリズム複雑度がO(N*logn)である(このように理解でき,交換ごとにN,合計logn回用いられる).しかし,ここではピボットの相対位置(Kの左または右)を決定した後,残りの半分を処理する必要はない.つまり,2回目の挿入アルゴリズムの複雑さはO(N)ではなくO(N/2)であるということは同じではないか.実は違います.次のプロセスは1+1/2+1/4+...<2です.言い換えれば、O(2 N)のアルゴリズム複雑度、つまりO(N)のアルゴリズム複雑度です.

 
def quicksort(num ,low ,high):  #    
    if low< high:
        location = partition(num, low, high)
        quicksort(num, low, location - 1)
        quicksort(num, location + 1, high)
 
def partition(num, low, high):
    pivot = num[low]
    while (low < high):
        while (low < high and num[high] > pivot):
            high -= 1
        while (low < high and num[low] < pivot):
            low += 1
        temp = num[low]
        num[low] = num[high]
        num[high] = temp
    num[low] = pivot
    return low
 
def findkth(num,low,high,k):   #      k  
        index=partition(num,low,high)
        if index==k:return num[index]
        if index<k:
            return findkth(num,index+1,high,k)
        else:
            return findkth(num,low,index-1,k)
 
 
pai = [2,3,1,5,4,6]
# quicksort(pai, 0, len(pai) - 1)
 
print(findkth(pai,0,len(pai)-1,0))

考え方3:ソートの挿入
k個の最大数を探すので、すべての数を完全にソートする必要はありません.k個の現在の最大数だけを保持するたびに、新しく来た要素を現在のk個のツリーの最小数と比較するたびに、新しい要素が大きい場合は配列に挿入し、そうでない場合はスキップします.サイクル終了後の配列の最小数は、k番目に大きい数を見つけることです.時間複雑度(n-k)logk

def Find_Kth_max(array,k):
    for i in range(1,k):
        for j in range(i,0,-1):
            if array[j] > array[j-1]:
                array[j],array[j-1] = array[j-1],array[j]
            else:
                pass
    for i in range(k,len(array)):
        if array[i] > array[k-1]:
            array[k-1] = array[i]
            for j in range(k-1,0,-1):
                if array[j] > array[j-1]:
                    array[j],array[j-1] = array[j-1],array[j]
                else:
                    pass
    return array[k-1]
            
print(Find_Kth_max([2,1,4,3,5,9,8,0,1,3,2,5],3))  

考え方4:スタックソート
kサイズの最小スタックを維持し、配列の各要素についてスタックトップのサイズを判断し、スタックトップが大きい場合は無視し、そうでない場合は、スタックトップをポップアップし、現在の値をスタックに挿入し、最小スタックを調整し続けます.時間複雑度O(n*logk)
1つ目:ライブラリ関数の使用

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return heapq.nlargest(k, nums)[-1]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k: 
                heapq.heappop(heap)
        return heapq.heappop(heap) # [5,6]            

第二種類:手動で積み上げる

def heap_build(parent,heap):
    child = 2*parent+1
    while child<len(heap):
        if child+1<len(heap) and heap[child+1]<heap[child]:
            child = child+1
        if heap[parent]<= heap[child]:
            break
        heap[parent],heap[child] = heap[child],heap[parent]
        parent,child = child,2*child+1
    return heap
    
def Find_heap_kth(array,k):
    if k > len(array):
        return None
    heap = array[:k]
    for i in range(k,-1,-1):
        heap_build(i,heap)
    for j in range(k,len(array)):
        if array[j]>heap[0]:
            heap[0] = array[j]
            heap_build(0,heap)
    return heap[0]
        
            
print(Find_heap_kth([2,1,4,3,5,9,8,0,1,3,2,5],6))