2020-04-06

针对215题，随机选择，找无序数组中第K 大的元素。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        i=nums
        def pp(la,l,r):
            if l==r:
                return l
            t=la[r]
            slow=l
            for d in range(l,r):
                if la[d]>=t:
                    la[slow],la[d]=la[d],la[slow]
                    slow+=1
            la[slow],la[r]=la[r],la[slow]
            return slow
        def d(arr,l,r,k):
            if l>=r:
                return arr[r]
            p=pp(arr,l,r)
            if p==k-1:  #这里很重要
                return arr[p]
            elif p>k-1:#这里很重要
                return d(arr,l,p-1,k)
            else:
                return d(arr,p+1,r,k)
        return d(i,0,len(i)-1,k)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        i=nums
        import random
        def f(w,l,r,k):
            if l>=r:return w[r]
            p=l
            b=random.randint(l,r)
            w[b],w[r]=w[r],w[b]  
            t=w[r]
            for d in range(l,r):
                if w[d]>=t: #这里很重要
                    w[p],w[d]=w[d],w[p]
                    p+=1
            w[p],w[r]=w[r],w[p]           
    
            if p==k-1:return w[p]
            elif p>k-1:return f(w,l,p-1,k)
            else:return f(w,p+1,r,k)
        return f(i,0,len(i)-1,k)

这里注意，非递归的实现，以及分区函数(独立写法)的左右双指针写法，以及逆序的写法。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        i=nums
        import random
        def pp(s,e):
            b=random.randint(s,e)
            i[b],i[e]=i[e],i[b]
            t=i[e]
            while s<e:
                # >= 这里很重要
                while s<e and i[s]>=t: s+=1
                i[e]=i[s]
                while s<e and i[e]<t:e-=1
                i[s]=i[e]
            i[s]=t
            return s

        def f(l,r,k):
            while 1:
                if l>=r:return i[r]
                #p=pp(l,r)

                s,e=l,r
                b=random.randint(s,e)
                i[b],i[e]=i[e],i[b]
                t=i[e]                
                while s<e:
                    #>=
                    while s<e and i[s]>=t:s+=1
                    i[e]=i[s]
                    while s<e and i[e]<t:e-=1
                    i[s]=i[e]
                i[s]=t
                p=s

                if p==k-1:return i[p]
                elif p>k-1:r=p-1
                else:l=p+1
        return f(0,len(i)-1,k)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        i=nums
        def pp(la,l,r):
            t=la[r]
            slow=l
            for d in range(l,r):
                if la[d]>=t:
                    la[slow],la[d]=la[d],la[slow]
                    slow+=1
            la[slow],la[r]=la[r],la[slow]
            return slow

        def d(arr,l,r,k):
            if l>=r:return arr[r]
            p=pp(arr,l,r)
            w=p-l+1 #这里很重要
            if w==k:return arr[p]
            elif w>k:return d(arr,l,p-1,k)
            else:return d(arr,p+1,r,k-w) #这里很重要

        return d(i,0,len(i)-1,k)

随机选择的另一种写法。