初学python的我开始Leetcode题-13

发布于：2025-07-17 ⋅ 阅读:(15) ⋅ 点赞:(0)

提示：100道LeetCode热题-13主要是堆相关，包括三题：数组中的第K个最大元素、前 K 个高频元素、数据流的中位数。由于初学，所以我的代码部分仅供参考。

前言

上一次，我们做的是栈的相关题目，这一次是堆。

堆(Heap)在计算机科学中是一种特殊的数据结构，具有以下核心特征：

  1. ​​数据结构特性​​：堆通常是一个可以被看作一棵完全二叉树的数组对象。它满足两个基本性质：

    • 堆中某个结点的值总是不大于(或不小于)其父结点的值

    • 堆总是一棵完全二叉树

  2. ​​逻辑与物理结构​​：

    • 物理结构本质上是顺序存储的，是线性的(使用数组实现)

    • 逻辑上不是线性的，是完全二叉树的逻辑存储结构

  3. ​​堆的类型​​：

    • ​​最大堆(Max Heap)​​：父节点的值大于或等于其子节点的值，堆顶元素是整个堆中的最大值

    • ​​最小堆(Min Heap)​​：父节点的值小于或等于其子节点的值，堆顶元素是整个堆中的最小值

  4. ​​存储表示​​：

    • 堆通常使用数组来表示完全二叉树

    • 对于节点i：

      • 父节点位置：(i-1)/2

      • 左子节点位置：2*i+1

      • 右子节点位置：2*i+2

  5. ​​基本操作​​：

    • 插入元素：将新元素添加到堆末尾，然后执行"上浮"操作(AdjustUp)调整堆结构

    • 删除元素：通常移除堆顶元素，将最后一个元素移到堆顶，然后执行"下沉"操作(AdjustDown)调整堆结构

而堆和栈如何区分呢?

  • ​​栈(Stack)​​：

    • 线性数据结构

    • 遵循后进先出(LIFO)原则

    • 只能在栈顶进行插入和删除操作

  • ​​堆(Heap)​​：

    • 树形数据结构(完全二叉树)

    • 没有固定的进出顺序规则

    • 通过堆序性(最大堆或最小堆)维护结构

提示：以下是本篇文章正文内容，下面结果代码仅供参考

题目1：数组中的第K个最大元素

1.题目要求：

题目如下：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 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^{5}

  • -10^{4} <= nums[i] <= 10^{4}

代码框架已经提供如下：

class Solution(object):

    def findKthLargest(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: int

        """

2.结果代码：

三向分区快速选择（处理重复元素）:堆解决方案虽然实现简单，但时间复杂度稍高。

import random

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def quick_select(left, right, k_largest):
            if left == right:
                return nums[left]
            
            # 随机选择基准值
            pivot_index = random.randint(left, right)
            pivot = nums[pivot_index]
            
            # 初始化指针
            lt = left      # 小于基准值的区域的右边界
            gt = right     # 大于基准值的区域的左边界
            i = left       # 当前遍历指针
            
            while i <= gt:
                if nums[i] > pivot:
                    nums[i], nums[gt] = nums[gt], nums[i]
                    gt -= 1
                elif nums[i] < pivot:
                    nums[i], nums[lt] = nums[lt], nums[i]
                    lt += 1
                    i += 1
                else:
                    i += 1
            
            # 此时数组分为三部分：
            # [left..lt-1] < pivot
            # [lt..gt] == pivot
            # [gt+1..right] > pivot
            
            left_count = lt - left          # 小于pivot的元素数量
            right_count = right - gt        # 大于pivot的元素数量
            mid_count = gt - lt + 1         # 等于pivot的元素数量
            
            if k_largest <= right_count:
                return quick_select(gt + 1, right, k_largest)
            elif k_largest > right_count + mid_count:
                return quick_select(left, lt - 1, k_largest - (right_count + mid_count))
            else:
                return pivot
        
        return quick_select(0, len(nums) - 1, k)

算法分析：

  • ​​时间复杂度​​：平均O(n)，最坏情况下O(n²)

  • ​​空间复杂度​​：O(logn)（递归栈空间）

然后发现这题Leetcode时间最快的是计数排序的一个代码，代码如下:

class Solution(object):
    def findKthLargest(self, nums, k):
    #     """
    #     :type nums: List[int]
    #     :type k: int
    #     :rtype: int
    #     """
        
    #     def quicksort(i,j,k):
    #         if i==j:
    #             return nums[i]
    #         pivot = nums[i]
    #         # nums[i],nums[(i+j)//2] = nums[(i+j)//2],nums[i]
    #         x,y = i,j 
    #         while x<y:
    #             while nums[y] <= pivot and  x<y:
    #                 if nums[y] == pivot:
    #                     y-=1
    #                     break
    #                 y-=1
    #             while nums[x] >= pivot and x<y:
    #                 if nums[x] == pivot:
    #                     x+=1
    #                     break
    #                 x+=1
    #             nums[x],nums[y] = nums[y],nums[x]
            
    #         nums[x],nums[i] = nums[i],nums[x]
    #         if x == k-1:
    #             return nums[x]
    #         elif x>k-1:
    #             res = quicksort(i,x-1,k) 
    #         else:
    #             res = quicksort(x+1,j,k)
    #         return res

        # i,j = 0,len(nums)-1
        # res  = quicksort(i,j,k)
        # return res
    # def findKthLargest(self, nums: List[int], k: int) -> int:
        # 使用计数排序
        # 统计数的范围 
        # -- 根据计数排序，还需统计数的范围，设定max-min+1的0值数组长度，且统计数时下标刚好-min来衡量
        # 本题已明确表明nums[i]范围为-10000-10000 因此可设定数组长度为20001
        count = [0] * 20001
        # 统计数组中每个值出现的次数
        for num in nums:
            count[num + 10000] += 1
        # 因为要找数组中第k个最大的元素，因此从后往前遍历 寻找第k个最大的
        cnt = 0
        for i in range(len(count)-1, -1,-1):
            cnt += count[i]
            if cnt >= k:
                return i - 10000

计数排序更快的原因可能有：

  1. ​​输入规模与范围的比例​​：

    • 当n（数组长度）与k（值范围）的比例较小时，计数排序特别高效

    • 题目中n可以达到10^{5}，而k是固定的20001，这使得计数排序非常适用

  2. ​​实现简单直接​​：

    • 计数排序实现非常直接：一次遍历计数，一次反向遍历找第k大元素

    • 没有复杂的控制流或递归调用，现代CPU可以高效执行

题目2：前 K 个高频元素

1.题目要求：

题目如下：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 10^{5}

  • k 的取值范围是 [1, 数组中不相同的元素的个数]

  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(nlogn) ，其中 n 是数组大小。

代码框架已经提供如下：

class Solution(object):

    def topKFrequent(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: List[int]

        """

2.结果代码：

哈希表统计 + 堆排序：

import heapq
from collections import Counter

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # 统计每个元素的频率
        count = Counter(nums)
        
        # 使用最小堆来维护前k个高频元素
        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)
        
        # 提取结果
        return [num for freq, num in heap]

  • 时间复杂度​​：O(n log k)，其中n是数组长度。统计频率需要O(n)时间，堆操作需要O(log k)时间，共进行n次

  • ​​空间复杂度​​：O(n)，用于存储哈希表和堆

而别人方法更快，可能是本题测试环境下基于字典和排序的实现确实会比基于堆的解决方案更快。

(1) 常数因子更小

  • 基于字典和排序的实现主要使用字典操作和简单的排序，这些操作的常数因子通常比堆操作小

  • 堆操作（尤其是Python的heapq）涉及更多的函数调用和对象创建，开销较大

(2) 输入特性影响

  • 当不同元素的数量m远小于n时（即很多重复元素），m log m会显著小于n log k

  • 例如，在极端情况下，如果数组中只有几种不同的数字，m会非常小

(3) Python实现细节

  • Python的list.sort()使用Timsort算法，对小规模数据特别高效

  • Python的heapq模块是用Python实现的，而list.sort()是用C实现的，后者更快

(4) 内存访问模式

  • 基于字典和排序的实现使用连续的内存访问（字典和列表），这对CPU缓存更友好

  • 堆操作涉及更多的随机内存访问，缓存命中率较低

class Solution:
    def topKFrequent(self, nums, k):
        # 使用字典统计数字出现次数
        time_dict = defaultdict(int)
        for num in nums:
            time_dict[num] += 1
        # 更改字典，key为出现次数，value为相应的数字的集合
        index_dict = defaultdict(list)
        for key in time_dict:
            index_dict[time_dict[key]].append(key)
        # 排序
        key = list(index_dict.keys())
        key.sort()
        result = []
        cnt = 0
        # 获取前k项
        while key and cnt != k:
            result += index_dict[key[-1]]
            cnt += len(index_dict[key[-1]])
            key.pop()

        return result[0: k]

题目3：数据流的中位数

1.题目要求：

题目如下：

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。

  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]


输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -10^{5} <= num <= 10^{5}

  • 在调用 findMedian 之前，数据结构中至少有一个元素

  • 最多 5 * 10^{4} 次调用 addNum 和 findMedian

代码框架已经提供如下：

class MedianFinder(object):

    def __init__(self):

       

    def addNum(self, num):

        """

        :type num: int

        :rtype: None

        """

2.结果代码：

import bisect

class MedianFinder(object):

    def __init__(self):
        self.nums = []

    def addNum(self, num):
        bisect.insort(self.nums, num)

    def findMedian(self):
        n = len(self.nums)
        if n % 2 == 1:
            return self.nums[n//2]
        return (self.nums[n//2-1] + self.nums[n//2]) / 2.0

  1. 数据结构​​：使用单个列表self.nums来维护所有元素，并通过bisect.insort保持列表有序

  2. ​​时间复杂度​​：

    • addNum操作：O(n)，因为bisect.insort虽然查找插入位置是O(log n)，但实际插入操作需要移动元素，是O(n)

    • findMedian操作：O(1)，直接通过索引访问中间元素

  3. ​​空间复杂度​​：O(n)，只需要存储所有元素

本题双堆法（也称为对顶堆法）也可高效实现，速度更优但内存消耗高于我刚刚的bisect实现。

总结

针对堆的三种题型进行了学习，了解了部分有关堆与python的相关知识，大家加油！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布