大数据平台 Shell脚本 软件测试工程师 Redis golang sorting sockets mtu原理 configuration path static vue自定义组件 angular视频 rxjava线程切换 matlab图像滤波 判断bigdecimal是否为空 java高级特性 python实例教程 python获取字典的值 javatrim java时间 java环境配置 java8函数式接口 java时间戳转时间 java读取文件数据 java获取本机ip java遍历set linux教学 计算机操作系统第四版 两表关联查询 python的用途 HTML5从入门到精通 数组删除指定元素 vscode全局搜索 sdm439 男网红头像 打印机怎么打印照片 js对象转字符串 电脑内录软件 机械换装
当前位置: 首页 > 学习教程  > 编程语言

力扣刷题Python笔记:前 K 个高频元素

2020/12/28 18:48:30 文章标签:

题目 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 提示: 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一&#x…

题目

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
在这里插入图片描述
提示:

  • 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。

来源:力扣(LeetCode)

Python解法

二叉堆与优先队列

这道题用到了二叉堆与优先队列的相关知识点。

二叉树本质是一种完全二叉树,它分为最大堆最小堆。最大堆的任何一个父节点,都大于等于它的左子节点或右子节点的值。最小堆的任何一个父节点,都小于等于它的左子节点或右子节点的值。二叉堆的根节点叫作堆顶,最大堆的堆顶是整个堆中的最大元素,最小堆的堆顶是整个堆中的最小元素。

队列的特点是先进先出(FIFO)。而优先队列不再遵循先入先出的规则,而是分为两类:最大优先队列和最小优先队列。最大优先队列是无论入队顺序如何,都是当前最大的元素优先出队。最小优先队列是无论入队顺序如何,都是当前最小的元素优先出队。

因此,我们可以结合以上两部分知识来解决这道题。具体思路如下:

  • 根据给定数组计算每个元素的个数并将其转换成列表的形式 stat,列表 stat 中的元素形式为 (某一种元素, 元素个数);
  • 因为最小堆是一种完全二叉树,我们假设完全二叉树是从索引 1 开始计算的,因此对于索引 i,它的左子节点索引是 2i,右子节点索引是 2i+1;
  • 创建最小堆 heap,在最开始插入一个占位节点 (0, 0),此时最小堆堆顶索引与数组 heap 索引为 1 的位置相同;
  • 读取 stat 中前 k 个元素,将其逐个放入数组 heap 中并利用上浮方法进行排序,最终二叉堆的规模为 k+1,多出来的1 为占位节点;
  • 依次读取 stat 中除前 k 个元素外剩下的元素,并判断该元素对应的元素个数是否大于二叉堆的堆顶,即是否 heap[1];
  • 如果大于,说明相比于 heap[1] 该元素更满足要求,将堆顶用该元素替换,然后将该元素逐渐下沉到它应在的位置;
  • 最后,排除占位节点输出 heap[1:] 即为所求结果。

代码如下:

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    def sift_down(arr, root, k):
        """下沉log(k),如果新的根节点>子节点就一直下沉"""
        val = arr[root] # 用类似插入排序的赋值交换
        while root<<1 < k:
            child = root << 1
            # 选取左右孩子中小的与父节点交换
            if child|1 < k and arr[child|1][1] < arr[child][1]:
                child |= 1
            # 如果子节点<新节点,交换,如果已经有序break
            if arr[child][1] < val[1]:
                arr[root] = arr[child]
                root = child
            else:
                break
        arr[root] = val

    def sift_up(arr, child):
        """上浮log(k),如果新加入的节点<父节点就一直上浮"""
        val = arr[child]
        while child>>1 > 0 and val[1] < arr[child>>1][1]:
            arr[child] = arr[child>>1]
            child >>= 1
        arr[child] = val

    stat = collections.Counter(nums)
    stat = list(stat.items())
    heap = [(0,0)]

    # 构建规模为k+1的堆,新元素加入堆尾,上浮
    for i in range(k):
        heap.append(stat[i])
        sift_up(heap, len(heap)-1) 
    # 维护规模为k+1的堆,如果新元素大于堆顶,入堆,并下沉
    for i in range(k, len(stat)):
        if stat[i][1] > heap[1][1]:
            heap[1] = stat[i]
            sift_down(heap, 1, k+1) 
    return [item[0] for item in heap[1:]]

本文链接: http://www.dtmao.cc/news_show_550117.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?