LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】

  • 题目描述:
  • 解题思路一:哈希表记录出现次数,然后用最小堆取,因为每次都是弹出最小的,剩下的一定是K个最大的。
  • 解题思路二:直接排序
  • 解题思路三:堆
  • 解题思路三:快速排序

题目描述:

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

示例 1:

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

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

提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

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

解题思路一:哈希表记录出现次数,然后用最小堆取,因为每次都是弹出最小的,剩下的一定是K个最大的。

import heapq # 默认是最小堆
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map_ = {}
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0) + 1
        pri_que = []
        for key, freq in map_.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k: 
                heapq.heappop(pri_que)
        result = [0] * k
        for i in range(k-1, -1, -1):
            result[i] = heapq.heappop(pri_que)[1]
        return result

时间复杂度:O(nlogk)
空间复杂度:O(n)

解题思路二:直接排序

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        return [item[0] for item in count.most_common(k)]

时间复杂度:O(nlogn)
空间复杂度:O(n)

解题思路三:堆

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        heap = [(val, key) for key, val in count.items()]
        return [item[1] for item in heapq.nlargest(k, heap)]

时间复杂度:O(nlogn)
空间复杂度:O(n)

解题思路三:快速排序

在这里插入图片描述

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        num_cnt = list(count.items())
        topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1)
        return [item[0] for item in topKs]
    
    def findTopK(self, num_cnt, k, low, high):
        pivot = random.randint(low, high)
        num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
        base = num_cnt[low][1]
        i = low
        for j in range(low + 1, high + 1):
            if num_cnt[j][1] > base:
                num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
                i += 1
        num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
        if i == k - 1:
            return num_cnt[:k]
        elif i > k - 1:
            return self.findTopK(num_cnt, k, low, i - 1)
        else:
            return self.findTopK(num_cnt, k, i + 1, high)

时间复杂度:O(n)
空间复杂度:O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/528211.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CentOS7安装MySQL8.0教程

环境介绍 操作系统&#xff1a;Centos7.6 MySQL版本&#xff1a; 8.0.27 只要是8.0.*版本&#xff0c;那就可以按照本文说明安装 一、安装前准备 1、卸载MariaDB 安装MySQL的话会和MariaDB的文件冲突&#xff0c;所以需要先卸载掉MariaDB。 1.1、查看是否安装mariadb rpm -…

SQL注入利用学习-Union联合注入

联合注入的原理 在SQL语句中查询数据时&#xff0c;使用select 相关语句与where 条件子句筛选符合条件的记录。 select * from person where id 1; #在person表中&#xff0c;筛选出id1的记录如果该id1 中的1 是用户可以控制输入的部分时&#xff0c;就有可能存在SQL注入漏洞…

自媒体内容创作助手:7款必备ai写作工具一览! #学习方法#科技#其他

这些工具不仅可以快速生成高质量的文本内容&#xff0c;还可以根据用户的需求进行个性化定制。它们可以帮助我们节省大量的时间和精力&#xff0c;让我们更加专注于创意和细节的打磨。本文将为大家详细介绍几个AI写作工具&#xff0c;让你在写作领域更上一层楼。 1.七燕写作 这…

【随笔】Git 高级篇 -- 撤销变更 reset | revert(十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

uniapp项目问题及解决(前后端互联)

1.路由跳转的问题 uni.navigateTo&#xff08;&#xff09; 保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面 uni.redirectTo&#xff08;&#xff09; 关闭当前页面&#xff0c;跳转到应用内的某个页面。 uni.reLaunch&…

探索未来产业:新技术、新商业、新趋势

引言 随着科技的迅速发展和全球经济的不断变化&#xff0c;未来产业已经成为全球关注的焦点之一。未来产业的兴起不仅代表着新的商业机遇&#xff0c;更是对传统产业模式的颠覆和重构。在这个充满挑战和机遇的时代&#xff0c;我们不得不认真思考未来产业的重要性和前景。 未…

STM32之HAL开发——FatFs文件系统移植

FatFs文件系统移植 FatFs 程序结构图 移植 FatFs 之前我们先通过 FatFs 的程序结构图了解 FatFs 在程序中的关系网络 用户应用程序需要由用户编写&#xff0c;想实现什么功能就编写什么的程序&#xff0c;一般我们只用到 f_mount()、f_open()、 f_write()、f_read() 就可以…

在【Cencos7】中安装【Nacos】并适配【PostgreSQL】数据库

在【Cencos7】中安装【Nacos-2.3.0】并适配【PostgreSQL】数据库 安装JDK wget命令下载&#xff1a; wget https://repo.huaweicloud.com/java/jdk/8u151-b12/jdk-8u151-linux-x64.tar.gz解压 tar -xzvf jdk-7u80-linux-x64.tar.gz将解压后的目录移动到/opt下 sudo mv jdk…

unity_Button:单击的三种实现方式

1.针对特定单个按钮 此代码直接绑定到button上面无需其他操作 using UnityEngine; using UnityEngine.UI;public class PrintHelloOnButtonClick : MonoBehaviour {private Button button;void Start(){// 获取当前GameObject上的Button组件button GetComponent<Button&g…

【Redis系列】Spring Boot 集成 Redis 实现缓存功能

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

[C语言]——动态内存管理

目录 一.为什么要有动态内存分配 二.malloc和free 1.malloc 2.free 三.calloc和realloc 1.calloc 2.realloc 3.空间的释放​编辑 四.常见的动态内存的错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟内存使用free释放 4.使用free释放⼀块…

嘉轩智能工业科技诚邀您参观2024第13届生物发酵展

参展企业介绍 自2005年成立以来&#xff0c;嘉轩一直致力于工业智能永磁滚筒的研发、制造及销售&#xff0c;具有十多年的从业经验&#xff0c;公司主营产品包括工业智能永磁滚筒、机电智能诊断、工业智能电机等&#xff0c;高效智能自驱动永磁滚筒为我公司目前主导产品&#x…

【C++】——list的介绍及使用 模拟实现

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 一、list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.…

CSS导读 (Emmet语法)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 续&#xff1a;七、Chrome调试工具 一、Emmet语法 1.1 快速生成HTML结构语法 1.2 快速生成CSS样式语法 &…

从概念到实践:揭开枚举与联合体在数字化创新时代的神秘面纱

欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 C语言知识 先赞后看&#xff0c;已成习惯 创作不易&#xff0c;多多支持&#xff01; 在编程的世界中&#xff0c;枚举和联合体是两种非常基础且重要的数据结构。它们各自具有独特的特点和用途&#xff0c;为程序员提供…

【人工智能】AI赋能城市交通 未来城市的驱动力

前言 随着城市化进程的不断加速&#xff0c;交通拥堵、环境污染等问题日益凸显&#xff0c;人们对交通系统的效率和可持续性提出了更高的要求。在这样的背景下&#xff0c;智能交通技术正成为改善城市交通的重要驱动力。本文将探讨智能交通技术在解决城市交通挑战方面的应用和未…

算法打卡26

今日任务&#xff1a; 1&#xff09;332.重新安排行程 2&#xff09;51.N皇后 3&#xff09;37.解数独 332.重新安排行程 题目链接&#xff1a;332. 重新安排行程 - 力扣&#xff08;LeetCode&#xff09; 给定一个机票的字符串二维数组 [from, to]&#xff0c;子数组中的两个…

Junit单元测试框架 --java学习笔记

单元测试 就是针对最小的功能单元(方法)&#xff0c;编写测试代码对其进行正确性测试 之前是如何进行单元测试的?有什么问题? 只能在main方法编写测试代码&#xff0c;去调用其他方法进行测试无法实现自动化测试&#xff0c;一个方法测试失败&#xff0c;可能影响其他方法…

Android Studio 生成 keystore 签名文件及打包验证流程

一、创建keystore签名文件 1、在菜单栏中&#xff0c;依次点击 Build - Generate Signed Bundle/Apk...(生成签名) 2、选择 APK 选项&#xff0c;点击按钮 Next 到下一步 3、新建key store秘钥文件&#xff0c;点击按钮 Next 到下一步 4、按如下提示填写信息&#xff0c;点击按…

微服务篇面试题

1、SpringCloud的组件有哪些&#xff1f; 2、负载均衡如何实现&#xff1f; 3、什么是服务雪崩&#xff1f;怎么解决&#xff1f; 4、项目中有没有做过限流&#xff1f; Tomcat单体可以&#xff0c;分布式不适合 5、解释一下CAP和BASE P&#xff1a;加入node03这边的网络断了&a…