[Leetcode]215. Kth Largest Element in an Array

これはLeetcodeの第215題で、無秩序な配列の第Kの大きい数を求めます.K番目の大きい/小さい数を求めるのも1つの経典の問題で、一般的に2つの方法があります:思想を積み上げて速く思想を並べます.その時間的複雑度はそれぞれ(O(NlogK))と(O(N))に達した.まずこの2つのアルゴリズムを解析し,次いで最適化アルゴリズムを解析した.
スタック
一般的に、K番目の大数を求めるには最小スタックを使用し、K小数を求めるには最大スタックを使用します.時間の複雑さはすべて(O(NlogK))です.Kサイズの最小スタックを維持し、配列内の各要素についてスタックトップのサイズを判断し、スタックトップが大きい場合は無視し、そうでない場合は、スタックトップをポップアップし、現在の値をスタックに挿入するという考え方です.スタックを更新するたびの時間は(logK)で、合計N個の数があるのでO(NlogK)です.コードは次のとおりです.

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        min_heap  = nums[:k]
        heapq.heapify(min_heap)  # create a min-heap whose size is k 
        for num in nums[k:]:
            if num > min_heap [0]:
                heapq.heapreplace(min_heap , num)
            # or use:
                # heapq.heappushpop(min_heap, num)
        return min_heap [0]

速排分治
高速ソートの考え方を利用して配列Sからランダムに1つの元素Xを探し出し,配列をSaとSbの2つの部分に分ける.Sa中の元素はX以上であり,Sb中の元素はX以下である.次の2つのケースがあります.

Sa中の元素の個数がkより小さい場合、Sb中の第k-|Sa|個の元素は第kの大きい数である.

Saの要素の個数がk以上であれば、Saのk番目の大きい数を返します.時間複雑度近似(O(n))

1本目の急行は見つからず、時間複雑度が(O(n))、2本目も見つからず、時間複雑度がO(n/2),…,k本目が見つかり、時間複雑度が(O(n/2 k))であるため、総時間複雑度は(O(n(1+1/2+....+1/2 k))=O(n))である.しかし、最悪の場合、時間的複雑度は(O(N^2))である.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        lo,hi = 0,len(nums)-1
        while lo=v and i=a[j] and j>lo:
                j-=1
            if (i>=j):break
            a[i],a[j] = a[j],a[i]
        a[lo],a[j] = a[j],a[lo]
        return j

BFPRTアルゴリズム
前の方法に加えて,分割要素をフィルタリングするプロセスを加えると,最悪の時間複雑度を(O(n))に下げることができる.フィルタリングの過程は,すべての数などを多くのセグメントに分割し,すべてのセグメントの中間値を求めることである.すべての中間値からなるセグメントを構成し、分割要素として中間値を取ります.すなわち、中間値の中間値を分割要素とする.中間値をとるには、各セグメントの長さが短く、複雑さに影響を与える主な要因ではないため、ソート方法を選択してから選択することができる.中間値の中間値をとり,再帰的な方法で自身を呼び出せばよい.これにより最悪時間の複雑度を(O(n))に下げることができ,複雑度証明は煩雑である.
BFRFTの本質は,分割値の選択を最適化することであり,ランダムに分割値を選択することではない.具体的な流れは以下の通りである:1、配列を5つのグループに分け、5つ未満の自動グループにする.グループ分割に要する時間はO(1)である.2、各グループをグループ内でソートし、ソートを挿入できます.ソート数は5個しかないので,時間的複雑度はO(1)と記すことができ,すべてのグループがO(N)とソートされる.3、各グループ内の上中位数を取得し、これらの上中位数を新しい配列mediumsに構成する.4、mediums配列中の上中位数pvalueを求め、ソートを使用せず、BFPRTを再帰的に呼び出すプロセスを用い、上中位数を求めることはmediums配列のmediums.size()/2番目の数を求めることである.5、このときに得られるpvalueは、選択した分割値であり、partitionプロセスを行えばよい.
なぜなら、配列長がnであると仮定するとmediums配列の長さがn/5であると、得られるpvalueはmediumではn/10の数がそれより小さくなり、このn/10の数は、自分の5の数のグループではpvalueよりも3の数が小さくなり、少なくともn/10*3、すなわち3 n/10の数がpvalueより小さくなり、最大7 n/10の数がpvalueよりも大きくなるからである.3 n/10の数を確実に淘汰することができます.このように区分するのは比較的均衡がとれている.
6、先ほどpvalue区分値を取得した後、partitionプロセスを行い、等しい領域の境界下標を返します.7、kが等しい範囲内であれば、pvalueを返す.kが領域に等しい左側にある場合、再帰的に左側が領域より小さい部分を呼び出す.kが領域に等しい右側にある場合、再帰呼び出しは領域より大きい部分である.

class Solution:
    def findKthSmallest(self, nums, k) :
        return self.bfprt(nums,0,len(nums)-1,k-1)

    def bfprt(self,nums,lo,hi,k):
        if lo == hi:
            return nums[lo]
        if hi-lo <= 5:
            return sorted(nums[lo:hi+1])[k-lo]
        pivot = self.medianOfMedians(nums,lo,hi)
        ind = lo+nums[lo:hi+1].index(pivot)
        range = self.partition(nums,lo,hi,ind)
        if k>=range[0] and k<=range[1]:
            return nums[k]
        elif k < range[0]:
            return self.bfprt(nums,lo,range[0]-1,k)
        else:
            return self.bfprt(nums,range[1]+1,hi,k)


    def medianOfMedians(self,nums,lo,hi):
        medians = []
        new = nums[lo:hi+1]
        for i in range(0,len(new),5):
            cur = sorted(new[i:i+5])
            mid = cur[len(cur)//2]
            medians.append(mid)
        return self.bfprt(medians,0,len(medians)-1,len(medians)//2)

    def partition(self, a, lo, hi,ind):
        a[ind],a[lo] = a[lo],a[ind]
        lt,gt = lo,hi
        i = lo+1
        v = a[lo]
        while i<=gt:
            if a[i] < v:
                a[i],a[lt] = a[lt],a[i]
                i+=1
                lt+=1
            elif a[i]>v:
                a[i],a[gt] = a[gt],a[i]
                gt -= 1
            else:
                i+=1
        return [lt,gt]

その中でpartitionの方法は速い3方向の切り分けの中のpartitionと見なすことができます.重複値の影響を除去するために、pivotの下限と上限、すなわち最初のpivotのインデックス(lt)と最後のpivotのインデックス(gt)を返します.1回のpartition後、(lt)左側はpivotより小さい値であり、(gt)右側はpivotより大きい値である.
拡張:
無秩序配列の中位数を求めます.
実際には配列を求めるtopN問題であり、配列長Lengthが奇数であれば、NはLength//2+1である.配列長が偶数の場合、NはLength//2+1、およびLength//2の数の平均値である.なお,この問題ではスタックを用いて解くことは,実際には(Nlogn)の複雑さであるため,一般的には高速配列やBFRFTアルゴリズムが用いられる.