Skip to content

Latest commit

 

History

History
576 lines (417 loc) · 17 KB

数据结构-堆、优先队列.md

File metadata and controls

576 lines (417 loc) · 17 KB
Raw

堆、优先队列

Problems

剑指Offer 4000 最小的k个数（partition操作） (简单, 2021-12)

优先队列 快排 经典 剑指Offer

问题简述 
输入整数数组 arr ，找出其中最小的 k 个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

详细描述 
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
    输入：arr = [3,2,1], k = 2
    输出：[1,2] 或者 [2,1]
示例 2：
    输入：arr = [0,1,2,1], k = 1
    输出：[0]
 
限制：
    0 <= k <= arr.length <= 10000
    0 <= arr[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：快排中的 partition 过程
  • 快排的过程：
    • partition 过程：以数组某个元素（一般取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
    • 递归地对左右部分执行 partition 过程，直至区域内的元素数量为 1；
  • 基于以上思想，当某次划分后基准数正好是第 k+1 小的数字，那么此时基准数左边的所有数字便是题目要求的最小的 k 个数。
Python 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

        def partition(lo, hi):  # [lo, hi]
            if lo >= hi: return

            p = arr[lo]  # 选取第一个位置为基准点
            l, r = lo, hi  # l 的初始位置应该在 lo，而不是 lo + 1
            # 假设初始化为 lo + 1，当 a[lo] 为最小值时，此时训处循环后 l == r == lo + 1，再交换 a[lo] 和 a[l] 就会出错

            while l < r:  # 退出循环时 l == r
                # 先移动 r，在移动 l，此时退出循环后 l 和 r 同时指向一个小于 p 的值；反之，如果用 a[hi] 初始化 p，就要先移动 l，在移动 r；

                # 从 r 开始，从右往左找到第一个 < p 的值，所以循环条件是 >=
                while l < r and arr[r] >= p: r -= 1
                # 从 l 开始，从左往右找到第一个 > p 的值，所以循环条件是 <=
                while l < r and arr[l] <= p: l += 1
                arr[l], arr[r] = arr[r], arr[l]
                
            arr[lo], arr[l] = arr[l], arr[lo]  # 将基准点移动到分界点

            if l < k: partition(l + 1, hi)
            if l > k: partition(lo, l - 1)

        partition(0, len(arr) - 1)
        return arr[:k]
思路2：堆（优先队列）
  • 写法1） 维护一个长度为 k 的大顶堆（第一个数最大），当下一个元素小于堆顶值，就更新堆（弹出堆顶，插入新值）；
  • 写法2） 直接对整个数组构建一个小顶堆，然后循环弹出前 k 个值；
  • 注意写法1 的时间复杂度是 O(NlogK)，而写法2 是 O(NlogN)；
Python：写法1（使用库函数） 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k < 1 or not arr:  # 使用堆，要添加非空断言
            return []

        import heapq

        # python 默认是小顶堆，且不支持自定义比较函数，所以要添加负号转成取前 k 大的数
        ret = [-x for x in arr[:k]]
        heapq.heapify(ret)

        for i in range(k, len(arr)):
            if -arr[i] > ret[0]:
                heapq.heappop(ret)
                heapq.heappush(ret, -arr[i])

        return [-x for x in ret]
Python：写法2（使用库函数） 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k < 1 or not arr:  # 使用堆，要添加非空断言
            return []

        import heapq

        # python 默认是小顶堆
        heapq.heapify(arr)

        ret = []
        for _ in range(k):
            ret.append(heapq.heappop(arr))

        return ret
思路3：计数排序
  • 因为题目限制了 arr[i] 的范围，所以还可以使用计数排序，时间复杂度 O(N)；
Python 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k >= len(arr):  # 使用计数排序要加长度判断
            return arr

        dp = [0] * 10001

        for x in arr:
            dp[x] += 1
        
        ret = []
        cnt = 0
        for i in range(len(dp)):
            while dp[i] and cnt < k:
                ret.append(i)
                cnt += 1
                dp[i] -= 1
            if cnt == k:
                return ret

剑指Offer 4100 数据流中的中位数 (困难, 2021-12)

设计 堆 剑指Offer

问题简述 
设计一个支持以下两种操作的数据结构：
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。
详细描述 
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。
示例 1：
    输入：
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出：[null,null,null,1.50000,null,2.00000]
示例 2：
    输入：
    ["MedianFinder","addNum","findMedian","addNum","findMedian"]
    [[],[2],[],[3],[]]
    输出：[null,null,2.00000,null,2.50000]
 
限制：
    最多会对 addNum、findMedian 进行 50000 次调用。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 分别使用一个大顶堆存放较小的一半（堆顶为其中的最大值），和一个小顶堆存放较大的一半（堆顶为其中的最小值）；
  • 动态保持两个堆的元素数量相等或差1（为了减少判断，可以始终保持固定的堆数量多1）
Python：优化前
  • 这份代码的逻辑非常直白，看上起也比较啰嗦；
import heapq

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lo = []  # 大顶堆，维护小于中位数的部分
        self.hi = []  # 小顶堆，维护大于中位数的部分
        self.cnt = 0  # 计数

    def addNum(self, num: int) -> None:
        if self.cnt == 0:  # 初始化
            heapq.heappush(self.hi, num)
            self.cnt += 1
            return

        if num > self.findMedian():  # to hi
            if self.cnt % 2:
                heapq.heappush(self.hi, num)
                tmp = heapq.heappop(self.hi)
                heapq.heappush(self.lo, -tmp)
            else:
                heapq.heappush(self.hi, num)
        else:  # to lo
            if self.cnt % 2:
                heapq.heappush(self.lo, -num)
            else:
                heapq.heappush(self.lo, -num)
                tmp = heapq.heappop(self.lo)
                heapq.heappush(self.hi, -tmp)

        self.cnt += 1

    def findMedian(self) -> float:
        if self.cnt % 2:
            return self.hi[0]
        else:
            return (-self.lo[0] + self.hi[0]) / 2
Python：优化后

数据流中的中位数（优先队列 / 堆，清晰图解）

from heapq import *

class MedianFinder:
    def __init__(self):
        self.hi = []  # 小顶堆，保存较大的一半
        self.lo = []  # 大顶堆，保存较小的一半

    def addNum(self, num: int) -> None:
        # 开始时，都为 0，先存入 self.lo，在转移到 self.hi
        if len(self.hi) == len(self.lo):
            heappush(self.lo, -num)
            heappush(self.hi, -heappop(self.lo))
        else:
            heappush(self.hi, num)
            heappush(self.lo, -heappop(self.hi))            


    def findMedian(self) -> float:
        if len(self.hi) != len(self.lo):
            return self.hi[0]
        else:
            return (-self.lo[0] + self.hi[0]) / 2

剑指Offer2 076 数组中的第K大的数字 (中等, 2022-02)

堆 分治 快排 剑指Offer2

问题简述 
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
详细描述 
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
示例 2:
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

提示：
    1 <= k <= nums.length <= 10^4
    -10^4 <= nums[i] <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xx4gT2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
思路1：partition操作（分治）
  • partition操作描述：先随机确定一个锚点，然后将数组划分为小于锚点和大于锚点的两部分呢；
import random


class Solution:
    """"""

    def findKthLargest(self, nums: List[int], k: int) -> int:  # noqa
        """"""
        lo, hi = 0, len(nums) - 1

        while True:  # 第 k 大，排序后期下标应该是 k - 1
            idx = self.partition(nums, lo, hi)
            if idx + 1 == k:
                return nums[idx]
            elif idx + 1 < k:
                lo = idx + 1
            else:
                hi = idx - 1

    def partition(self, nums: List[int], lo: int, hi: int) -> int:
        """"""
        # === 挑选锚点 ===
        # 方式1）默认选 lo 作为锚点
        # pivot = nums[lo]

        # 方式2）随机选择一个锚点，并把锚点固定到首位或末位，这里交换到首位
        flag = random.randint(lo, hi)
        pivot = nums[flag]
        nums[flag], nums[lo] = nums[lo], nums[flag]

        # === partition 操作 ===
        # 方式1）单向遍历
        idx = lo  # 记录锚点在数组中的升序顺位
        for i in range(lo + 1, hi + 1):
            if nums[i] > pivot:  # 找到一个大于锚点的值
                idx += 1
                nums[idx], nums[i] = nums[i], nums[idx]

        nums[idx], nums[lo] = nums[lo], nums[idx]  # 把锚点交换到 idx 的位置

        return idx

        # 方式2）左右交换
        # l, r = lo, hi
        # while l < r:
        #     while l < r and nums[r] <= pivot:
        #         r -= 1
        #     while l < r and nums[l] >= pivot:
        #         l += 1
        #     if l < r:
        #         nums[l], nums[r] = nums[r], nums[l]
        # nums[lo], nums[l] = nums[l], nums[lo]
        #
        # return l
思路2：大顶堆（Python，调库） 
import heapq


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """"""
        heap = []
        
        for x in nums:
            heapq.heappush(heap, -x)  # 默认是小顶堆，这里传入 -x，模拟大顶堆
            
        for _ in range(k - 1):
            heapq.heappop(heap)
            
        return -heap[0]

牛客 0051 合并k个已排序的链表 (较难, 2022-03)

堆 牛客

问题简述 
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
思路：堆/优先队列
写法1：不重载运算符，利用 tuple 排序 
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0  # 一个自增变量，避免直接对 node 排序
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        cur = dummy = ListNode(0)
        while h:
            _, _, node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        return dummy.next
写法2：重载运算符 
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0
        
        # 重载运算符
        def lt(a, b):
            return a.val < b.val
        ListNode.__lt__ = lt

        # 下面的写法也可以，但是不推荐，因为 lambda 表达式是不支持序列化的
        # ListNode.__lt__ = lambda a, b: a.val < b.val
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, node)
        
        cur = dummy = ListNode(0)
        while h:
            node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, node)
        
        return dummy.next