Leetcode 215. 数组中的第K个最大元素

方法一：快速排序变种

其实就是快速排序中的partition方法，该方法可以确定pivot在排序后数组中的位置（即pivot左边的数都比它小，右边的数都比它大），且返回pivot对应的index

class Solution(object):

    def findKthLargest(self, nums, k):
 
        n = len(nums)

        def quiksort(left, right): # 快排，将第一个数放到正确的位置上
            pivot = nums[left]
            point = left
            for i in range(left + 1, right + 1):
                if nums[i] < pivot:
                    point += 1
                    nums[point], nums[i] = nums[i], nums[point]
            nums[point], nums[left] = nums[left], nums[point]
            return point

        left, right = 0, n - 1
        while left <= right:
            loc = quiksort(left, right)
            if loc == n - k:
                return nums[loc]
            elif loc < n - k:
                left = loc + 1
            else:
                right = loc - 1

f(n) = f(n/2) + n 根据主定理，时间复杂度O(n)

方法二：最大堆

python的heapq类，构建最小堆

方法：

heapq.heappush(heap, item)

Push the value item onto the heap, maintaining the heap invariant.

heapq.heappop(heap)

Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].

heapq.heappushpop(heap, item)

Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().

heapq.heapify(x)

Transform list x into a heap, in-place, in linear time.

heapq.nlargest(n, iterable, key=None)

Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key, reverse=True)[:n].

heapq.nsmallest(n, iterable, key=None)

Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key)[:n].

import heapq
def get_top(data, num):

    # 维护一个大小为k的最大堆
    # 可以支持 items 为一个 dict 或 tuple
    # data: dict
    # k: int
    # return: top_k

    heap = []
    i = 0
    for key, value in text.items():
        if i < num:
            heapq.heappush(heap, (value, key))
            i += 1
        else:
            heapq.heappushpop(heap, (value, key))
    top = {}

    # 重新组合 dict
    for item in heap:
        top[item[1]] = item[0]
    return top

本题解答：

solution 1

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        heap = []
        for i in range(len(nums)):
            if i < k:
                heapq.heappush(heap, nums[i]) # 构建大小为k的小顶堆
            else:
            # 将小的元素出队，保留下的元素都是较大的，其中小的排在前面
                heapq.heappushpop(heap, nums[i]) 
        return heap[0]

solution 2

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

二者实现方式基本相同，写法不一样。时间复杂度 : O(Nlogk)

Leetcode 215

Leetcode 215. 数组中的第K个最大元素

方法一：快速排序变种

方法二：最大堆

solution 1

solution 2

CATALOG

FEATURED TAGS