字节青训-查找热点数据问题

news/2024/10/29 18:33:41/

问题描述

给你一个整数数组 nums 和一个整数 k,请你返回其中出现频率前 k 高的元素。请按升序排列。

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

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

 

测试样例

样例1:

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

样例2:

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

样例3:

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

解题思路: 

用一个去重的数组对每一个出现的数字计数然后按顺序得出前n个数字就行

数据结构

具体来说,用unordered_map 记录每个数字的频率。


然后将map中的数据添加到 vector 向量中。


接着是排序: 使用 sort 函数对 result 向量进行排序,排序依据是元素的频率(降序)。

输出格式的转换:


构建返回字符串: 遍历排序后的 result 向量的前 k 个元素,将它们转换为字符串并使用逗号分隔,

存储在 stringstream 中。

返回结果: 将 stringstream 中的内容转换为字符串并返回。

C++代码如下:

#include <iostream>  
#include <vector>  
#include <unordered_map>  
#include <queue>  
#include <sstream>  
#include <algorithm>  using namespace std;  string topKFrequent(vector<int>& nums, int k) {  // 使用哈希表记录每个元素的频率  unordered_map<int, int> freqMap;  for (int num : nums) {  freqMap[num]++;  }  vector<pair<int,int>> result;for(auto x : freqMap){result.push_back(x);}sort(result.begin(), result.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;});stringstream ss;for (size_t i = 0; i < k; ++i) {  ss << result[i].first;  if (i < k - 1) {  ss << ",";  }  }return ss.str();
}   int main() {//  You can add more test cases herestd::vector<int> nums1 = {1, 1, 1, 2, 2, 3};std::vector<int> nums2 = {1};//cout << topKFrequent(nums1, 2) << endl;std::cout << (topKFrequent(nums1, 2) == "1,2") << std::endl;std::cout << (topKFrequent(nums2, 1) == "1") << std::endl;return 0;
}

Python代码如下:

python">from collections import Counterdef solution(nums, k):# 使用Counter记录每个元素的频率freq_map = Counter(nums)# 将频率map转化为列表,并先按频率降序,再按元素值升序排序result = sorted(freq_map.items(), key=lambda x: (-x[1], x[0]))# 获取频率最高的前k个元素top_k = [result[i][0] for i in range(k)]return top_kif __name__ == "__main__":# 测试用例nums1 = [1, 1, 1, 2, 2, 3]nums2 = [1]nums3 = [4, 4, 4, 2, 2, 2, 3, 3, 1]# 输出测试结果print(solution(nums1, 2) == [1, 2])  # 输出: Trueprint(solution(nums2, 1) == [1])  # 输出: Trueprint(solution(nums3, 2) == [2, 4])  # 输出: True

 通过咯,感觉这个困难题的难度一般,主要是输出的格式需要自己去转换

这么一看python这么短,真是派派又森森呀~


http://www.ppmy.cn/news/1542893.html

相关文章

高级java每日一道面试题-2024年10月22日-JVM篇-JVM堆栈概念,何时销毁对象?

如果有遗漏,评论区告诉我进行补充 面试官: JVM堆栈概念,何时销毁对象? 我回答: JVM堆栈概念 栈&#xff08;Stack&#xff09;&#xff1a; 定义&#xff1a;栈是Java虚拟机为每个线程分配的内存区域&#xff0c;用于存储线程执行时的局部变量、操作数栈、动态链接和方法返…

Uefi Application小游戏开发之猜箱子

小游戏之猜箱子 选择箱子个数 &#xff0c;交换次数 &#xff0c;交换速度等&#xff0c;将球丢入到一个箱子中&#xff0c;然后开始随机交换箱子&#xff0c;猜出球的位置 源代码如下&#xff1a; #include <Uefi.h> #include <Library/UefiLib.h> #include &…

pip 和 pipx 的主要区别?

特性pippipx用途用于安装Python库或命令行应用程序&#xff0c;可以安装带entry points的库专门用于安装和管理Python命令行工具&#xff0c;每个工具都在隔离的虚拟环境中运行虚拟环境不自动创建虚拟环境&#xff0c;需要手动使用 venv 或 virtualenv 创建自动为每个安装的工具…

PHP免杀详细讲解PHP免杀详细讲解

基础学习 可变参数 $_GET $_POST $_COOKIE $_REQUEST $_SERVER 其中的某些参数可控,如REQUESTMETHOD,QUERYSTRING,HTTPUSERAGENT等 session_id() 这个比较特殊,但是依然可以利用 $_FILE $GLOBALS getallheaders() get_defined_vars() get_defined_functions() fil…

无人机动态窗口路径规划算法!

一、算法原理 DWA算法将局部路径规划问题描述为速度矢量空间上的约束优化问题。它根据无人机的当前状态&#xff08;如位置、速度、加速度等&#xff09;和环境信息&#xff08;如障碍物位置、目标点位置等&#xff09;&#xff0c;在速度空间内采样多组线速度和角速度&#x…

MongoDB-Plus

MongoDB-Plus是一款功能强大的数据库工具&#xff0c;它基于MongoDB&#xff0c;提供了更丰富的功能和更便捷的操作方式。以下是一篇关于MongoDB-Plus轻松上手的详细指南&#xff0c;旨在帮助初学者快速掌握其安装、配置和基础操作。 一、MongoDB-Plus概述 MongoDB是一款由C编…

linux中各目录作用及介绍

目录 1 /usr 1 /usr /usr 是 Unix-like 操作系统中的一个重要目录之一&#xff0c;代表可共享的用户资源&#xff08;User System Resources&#xff09;或 Unix Software Resource&#xff08;UNIX 软件资源&#xff09;。 /usr 目录通常包含了系统的许多可共享资源&#xf…

docker 安装 PostgreSQL

参考链接 https://hub.docker.com/_/postgres 安装 # 后台运行&#xff0c;镜像名称为 postgres # --name postgres 容器名称为 postgres # POSTGRES_PASSWORD 超级用户的密码&#xff0c;超级用户名默认为&#xff1a;postgres&#xff0c;可以使用 POSTGRES_USER 环境变量设…