题目

01-215-数组中的第K个最大元素

01-215-数组中的第K个最大元素

leetcode-215

• 输入：nums数组，k，k>=1，而非k从0开始
• 输出：排序后，第k大的元素，O(n)

示例

• [1, 2, 3, 3, 4, 5, 5, 6]，第4大 是4，而非3

快速选择第k大值

快速选择第k大值

快速排序

• 随机选择基准值pivot，把数组分为 < pivot 和 > pivot的两部分，分别进行递归。

快速选择

• 随机选择pivot，把数组分为：small(<p)、equal(=p)、big(>p) 3部分。

• 通过比较第k大和各部分长度，来确定递归查找范围

• 第k大 在big里：在big子数组里找, quick_select_big(big, k)

  $$k\le \text{len}(big)$$

• 第k大 在equal里：返回 pivot

  $$\text{len}(big)\le k\le \text{len}(big)+\text{len}(equal)$$

• 第k大 在small里：计算newk，在small子数组里找，quick_select_big(small, newk)

  $$\text{len}(big)+\text{len}(equal)<k$$$$newk=k-\text{len}(big)-\text{len}(equal)$$

def quick_select_big(self, nums: List[int], k: int) -> int:
    """快速选择，第k大的元素"""
    pivot = random.choice(nums)

    small = [v for v in nums if v < pivot]
    equal = [v for v in nums if v == pivot]
    big = [v for v in nums if v > pivot]

    if k <= len(big):
        # 第k大，在big范围里
        return self.quick_select_big(big, k)  
    elif len(big) < k <= len(big) + len(equal):
        # 正好落在equal区间
        return pivot  
    else:
        # 落在small区间，减去已经占用的排名
        newk = k - len(big) - len(equal) 
        return self.quick_select_big(small, newk)  

最小堆获取第k大值

最小堆获取第k大值

• 前k元素 建堆，默认为最小堆
• 遍历后续每一个元素val：若val>堆顶元素，val入堆。
• 返回heap[0] 堆顶元素，即为第k大值

def findKthLargest_heap(self, nums: List[int], k: int) -> int:
    # 使用前k个元素，初始化大小为k的堆
    min_heap = nums[:k]
    # o(k) 建堆
    heapq.heapify(min_heap)

    # 遍历剩余元素，进行淘汰
    for val in nums[k:]:
        # 当前值，大于堆顶元素，大于当前k个的最小值，则入堆
        if val > min_heap[0]:  
            # 弹出旧元素，新元素入堆，O(log k)
            heapq.heappushpop(min_heap, val)  
    # 直接返回堆顶元素，即为数组第k大值
    return min_heap[0]

桶排序获得第k大值

桶排序获得第k大值

• 数组取值范围：[-10000, 10000]，共N=20001个取值。
• 桶排序：建立大小为N的计数数组，遍历数组
  • 若某位置 对应数字出现，则计数+1
  • 由于有负数，使用偏移量OFFSET=10000 计算位置：idx = num + OFFSET
• 再从大到小遍历计数数组，累计count_sum，第k次遍历，即为第k大数字。
  • 不重复数组：k == count_sum
  • 但数组会重复：k <= count_sum
  • 比如：k=4, 前面是 4 4 5 5 6，上一轮count_sum=3, 当前count_sum=5

def findKthLargest_count_bucket(self, nums: List[int], k: int) -> int:
    """桶排序，计数，获得第k大元素"""

    # 数组范围 [-10000, 10000]
    OFFSET = 10000
    count_slots = [0] * 20001

    # 遍历数组，存储每个数字出现的次数
    for num in nums:
        idx = num + OFFSET
        count_slots[idx] += 1

    # 取第k大数字，倒序遍历 count_slots数组
    count_sum = 0
    for idx in range(len(count_slots)-1, -1, -1):
        # 当前位置有值
        if count_slots[idx] > 0:
            count_sum += count_slots[idx]
            # 不重复数组，k应该等于count_sum
            # if k == count_sum
            # 但可能会有重复，比如k=4, 前数字分别是 4 4 5 5 6，上一轮count_sum=3, 当前count_sum=5
            if k <= count_sum:  
                num = idx - OFFSET
                return num
    return -1

02-347-前K个高频元素

02-347-前K个高频元素

leetcode-347

• 输入：nums, k。数组长度 [1, 100000]
• 输出：前k个高频元素，O(n logn)
• [1,2,1,2,1,2,3,1,3,2], k=2 --> [1, 2]

Hash计数+堆排序获取前k个高频元素

Hash计数+堆排序获取前k个高频元素

• count计数统计频次
• 构建最小堆, heap=[]
• 遍历num及频次
  • 当前堆长度 < k，(cnt, num) 直接入堆
  • 否则，如果当前次数>堆顶次数，则heappushpop 旧出堆新入堆。

def topKFrequent_heap(self, nums: List[int], k: int) -> List[int]:
    """统计nums数组中高频的k个元素，count计数+最小堆"""
    counter = Counter(nums)

    heap = []
    # 遍历数组，入堆，出堆
    for num, cnt in counter.items():
        if len(heap) < k:
            # 堆长度不足，直接入堆。
            # 列表比较大小：先比较第一个元素，因此第一个元素必须是cnt
            heapq.heappush(heap, (cnt, num))  
        else:
            # 当前频次，高于堆顶元素，需新入堆旧出堆
            if cnt > heap[0][0]:
                heapq.heappushpop(heap, (cnt, num))  

    # 直接返回堆里的所有num元素
    res = [num for cnt, num in heap]
    return res

Hash计数+桶排序获取前k个高频元素

Hash计数+桶排序

• counter 计数。
• 桶：[0, 1, 2, 3, ...]，idx位置 存放频次=idx的数字列表
• 取前k个高频元素：从高到低取即可。

def topKFrequent_bucket(self, nums: List[int], k: int) -> List[int]:
    """统计nums数组前k个高频的元素，使用counter计数+桶排序，桶idx存放频次=idx的数组。nums长度 [1, 100000]"""
    counter = Counter(nums)
    MAX_LENGTH = 100000

    # bucket[idx] = [], 代表频次=idx的nums数组
    bucket = [[] for i in range(MAX_LENGTH+1)]

    # 存放到桶中
    for num, freq in counter.items():
        bucket[freq].append(num)

    # 前k个高频的数字
    res = []
    # 从高到低遍历桶
    for i in range(MAX_LENGTH, 0, -1):
        # 当前i有值，则放入res中
        if bucket[i]:
            res.extend(bucket[i])
        # 高频数组长度已到达k，则直接返回
        if len(res) >= k:
            return res[:k] 
    return res

03-295-数据流的中位数

03-295-数据流的中位数

leetcode-295

• 实现MedianFinder类，包括 init、addNum、findMedian三个方法。

最小堆+最大堆搭配算中位数

最小堆+最大堆搭配算中位数

两堆思想

• 定义最大堆、最小堆，保证把nums从中间分为左右2部分，长度均等。
  • 数量均衡：大顶堆数量 == 小顶堆数量，或多1
  • 大小有序：大顶堆堆顶 <= 小顶堆堆顶，左边矮于右边

中位数计算

• 总数为奇数：中位数=最大堆堆顶 左边最大元素
• 总数为偶数：中位数= (最大堆堆顶+最小堆堆顶) / 2，二堆顶元素求平均

addNum方法

• 大顶堆数量 == 小顶堆数量

  • 先入小顶堆，再弹出小顶堆最小元素，放到大顶堆。

• 大顶堆数量 == 小顶堆数量 + 1

  • 先入大顶堆，再弹出大顶堆最大元素，放到小顶堆。

class MedianFinder:

def __init__(self):
    # 最大堆存放左边元素，最小堆存放右边元素，从小到大
    # 保证最大堆元素-最小堆元素 <= 1
    self.max_heap = []
    self.min_heap = []

def addNum(self, num: int) -> None:
    """新元素入堆，根据数量放到左边或右边"""
    if len(self.max_heap) == len(self.min_heap):
        # 新元素应该放到左边，最大堆
        # 先放到最小堆，并弹出新的堆顶元素
        val = heapq.heappushpop(self.min_heap, num)
        # heapq默认是最小堆，因此放入-val，实现最大堆
        heapq.heappush(self.max_heap, -val)
    elif len(self.max_heap) == len(self.min_heap) + 1:
        # 新元素应该放到右边最小堆
        # 先放到左边最大堆，弹出新的左边最大值
        val = heapq.heappushpop(self.max_heap, -num)
        val = -val
        # 放到右边最小堆
        heapq.heappush(self.min_heap, val)
    return

def findMedian(self) -> float:
    """取中位数，根据整体数量来判断怎么取"""
    total_len = len(self.max_heap) + len(self.min_heap)
    if total_len % 2 == 0:
        # 整体为偶数，左右各堆顶取平均
        left_val = - self.max_heap[0]
        right_val = self.min_heap[0]
        return (left_val+right_val) / 2
    else:
        # 整体为奇数，取左边最大堆堆顶元素
        return -self.max_heap[0]