215 无序数组第K大的数 – Python量化投资

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)
「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!