215 无序数组第K大的数

leetcode解答

快排的思想，O(N)。n+n/2+n/4+...=2n= O(n)

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return

        import random
        p = random.choice(nums)

        left = [x for x in nums if x > p]
        mid = [x for x in nums if x == p]
        right = [x for x in nums if x < p]

        nums = left + mid + right
        li, ri = len(left), len(left) + len(mid)

        if k <= li:
            return self.findKthLargest(nums[:li], k)
        elif k > ri:
            return self.findKthLargest(nums[ri:], k - ri)
        else:
            return nums[li]

小根堆，O(N logK)，python默认小根堆

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        import heapq
        pq = []
        for item in nums:
            heapq.heappush(pq, item)
            if len(pq) > k:
                heapq.heappop(pq)
        return heapq.heappop(pq)