Lc 215 topk to quicksort

type

status

date

slug

summary

category

icon

password

215 topk 寻找第k大的元素

1.暴力排序

堆排序

快排思想


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick(nums,l,r,target):
            if l == r:
                return nums[target]
            p = nums[l]
            i = l - 1 
            j = r + 1
            while i < j:
                while True:
                    i+=1
                    if nums[i] >= p:
                        break
                while True:
                    j -=1       
                    if nums[j] <= p:
                        break
                if i < j:
                    nums[i],nums[j] = nums[j],nums[i]
            # can not use i here, because the pivot is nums[l] not nums[r]
            # but how to prove it ?
            if target<=j:
                return quick(nums,l,j,target)     
            else:
                return quick(nums,j+1,r,target)
        n = len(nums)
        return quick(nums,0,n-1,n-k)

我发现上述代码中不能使用i作为切分点，在我最开始的理解中，快排就是选一个pivot然后将小于等于pivot的放左边，大于的放右边，然后递归，每次能够将pivot放到最终的位置。为什么这里j可以作为切分点，但是i却不行呢？

考虑[5,6,4]这个数组，当i，j停下时，i=1，j=0，数组变为[4,6,5]，并不符合去认为的左右划分，使用i的话看不出有什么性质。j却可以成为一个划分点，nums[l;j] ≤ pivot < nums[j+1:r]。

ps：使用lomuto-partition最后一个case（元素全相等）会超时。

翻了翻算法导论，quicksort书中描述的partition算法是 lomuto-partition。在习题里给出了hoare-partition，正是上述算法，其返回j，作为划分点。

Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average. Also, as mentioned, the implementation given creates a balanced partition even when all values are equal, which Lomuto's scheme does not. Like Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to $ for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e. . Like others, Hoare's partitioning doesn't produce a stable sort. In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion. Therefore, the next two segments that the main algorithm recurs on are (lo..p) (elements ≤ pivot) and (p+1..hi) (elements ≥ pivot) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme.

请注意hoare返回的j不是pivot的下标，而是划分点的下标，或者说是新pivot的下标。

最后给出topk堆的算法


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        ns = list(map(lambda x: -x, nums))
        print(ns)
        
        heapq.heapify(ns)
        ans = 0
        for i in range(k):
            ans = heapq.heappop(ns)

        return -ans

Ref

https://sites.math.rutgers.edu/~ajl213/CLRS/Ch7.pdf

https://en.wikipedia.org/wiki/Quicksort