当前位置: 首页 > news >正文

leetcode347.前k个高频元素

leetcode347.前k个高频元素

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

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

优先队列法

struct hash_table {int key;int val;UT_hash_handle hh;
};//表示一个哈希表条目,包含key和val字段。
//定义一个指向hash_table结构的指针。
typedef struct hash_table* hash_ptr;struct pair {int first;int second;
};//表示一对整数。struct pair* heap;//用作堆的整数对数组。
int heapSize;//堆的大小的变量。void swap(struct pair* a, struct pair* b) {struct pair t = *a;*a = *b, *b = t;
}bool cmp(struct pair* a, struct pair* b) {return a->second < b->second;
}struct pair top() {//返回堆顶元素。return heap[1];
}int push(hash_ptr x) {//将新元素推入堆并维护堆属性。heap[++heapSize].first = x->key;heap[heapSize].second = x->val;int p = heapSize, s;while (p > 1) {s = p >> 1;if (cmp(&heap[s], &heap[p])) return 0;swap(&heap[p], &heap[s]);p = s;}return 1;
}int pop() {heap[1] = heap[heapSize--];int p = 1, s;while ((p << 1) <= heapSize) {s = p << 1;if (s < heapSize && cmp(&heap[s + 1], &heap[s])) s++;if (cmp(&heap[p], &heap[s])) return 0;swap(&heap[p], &heap[s]);p = s;}return 1;
}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {hash_ptr head = NULL;hash_ptr p = NULL, tmp = NULL;for (int i = 0; i < numsSize; i++) {//遍历数组,计算每个元素出现频率,并将其存储在哈希表中HASH_FIND_INT(head, &nums[i], p);if (p == NULL) {p = malloc(sizeof(struct hash_table));p->key = nums[i];p->val = 1;HASH_ADD_INT(head, key, p);} else {p->val++;}}//堆初始化heap = malloc(sizeof(struct pair) * (k + 1));heapSize = 0;/*如果堆的元素个数等于 k,则检查堆顶与当前出现次数的大小。如果堆顶更大(小根堆堆顶元素为最小值),说明至少有 k个数字的出现次数比当前值大,故舍弃当前值;否则,就弹出堆顶,并将当前值插入堆中。*//*HASH_ITER(hh, head, p, tmp) {//查找前k个频繁元素if (heapSize == k) {//堆已满(大小 == k)struct pair tmp = top();if (tmp.second < p->val) {//将堆顶元素与当前元素进行比较pop();//当前元素的频率更高,它会替换堆顶元素。push(p);//将p推入堆中}} else {push(p);//堆大小不等于k直接入栈}}/*它从堆中检索顶部元素并将其存储在临时变量 tmp 中。它从堆中弹出顶部元素。它将 tmp 的第一个值赋给数组 ret 的第 i 个元素。*//**returnSize = k;int* ret = malloc(sizeof(int) * k);for (int i = k-1; i >=0; i--) {//逆序输出堆元素struct pair tmp = top();pop();ret[i] = tmp.first;}return ret;
}

暴力法

#include <stdio.h>
#include <stdlib.h>// 结构体用于存储元素和其出现的频率
typedef struct {int num;int freq;
} Element;// 比较函数,用于qsort排序
int compare(const void *a, const void *b) {return ((Element *)b)->freq - ((Element *)a)->freq;
}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {// 统计每个元素的频率Element *elements = (Element *)malloc(numsSize * sizeof(Element));int count = 0;for (int i = 0; i < numsSize; i++) {int j;for (j = 0; j < count; j++) {if (elements[j].num == nums[i]) {elements[j].freq++;break;}}if (j == count) {elements[count].num = nums[i];elements[count].freq = 1;count++;}}// 对元素按频率进行排序qsort(elements, count, sizeof(Element), compare);// 返回前k个高频元素int *result = (int *)malloc(k * sizeof(int));*returnSize = k;for (int i = 0; i < k; i++) {result[i] = elements[i].num;}free(elements);return result;
}

相关文章:

leetcode347.前k个高频元素

leetcode347.前k个高频元素 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2: 输入: nums [1], k 1 输出: [1] 优先队列法 struct hash_…...

c++(二)

1. 类和对象 1.1. 封装 封装的意义 将属性和行为作为一个整体&#xff0c;表现生活中的事物&#xff1b;将属性和行为加以权限控制 public -> 公共权限&#xff1a;类内可以访问&#xff0c;类外也可以访问protected -> 保护权限&#xff1a;类内可以访问&#xff0c;…...

基于PHP的初中数学题库管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的初中数学题库管理系统 一 介绍 此初中数学题库管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;系统角色分为学生&#xff0c;教师和管理员。(附带参考设计文档) 技术栈&#xff1a;phpmysqlphpstudyvscode 二 功能 …...

WDG看门狗

1 WDG 1.1 简介 WDG是看门狗定时器&#xff08;Watchdog Timer&#xff09;的缩写&#xff0c;它是一种用于计算机和嵌入式系统中的定时器&#xff0c;用来检测和恢复系统故障。 看门狗就像是一个忠诚的宠物狗&#xff0c;它时刻盯着你的程序&#xff0c;确保它们正常运行。…...

zabbix server client 安装配置

Zabbix Server 采用源码包部署&#xff0c;数据库采用 MySQL8.0 版本&#xff0c;zabbix-web 使用 nginxphp 来实现。具体信息如下&#xff1a; 软件名 版本 安装方式 Zabbix Server 6.0.3 源码安装 Zabbix Agent 6.0.3 源码安装 MySQL 8.0.28 yum安装 Nginx 1.20…...

Unity关于Addressables.Release释放资源内存问题

前言 最近在编写基于Addressables的资源管理器&#xff0c;对于资源释放模块配合MemoryProfiler进行了测试&#xff0c;下面总结下测试Addressables.Release的结论。 总结 使用Addressables.Release释放资源时&#xff0c;通过MemoryProfiler检查内存信息发现加载的内容还在…...

运算放大器(运放)带宽和带宽平坦度

运算放大器带宽和带宽平坦度 电压反馈型运算放大器的带宽 下图1显示电压反馈型运算放大器的开环频率响应。有两种可能&#xff1a;图1A是最常见的情况&#xff0c;高直流增益以6dB/倍频程从极低频率下降至单位增益&#xff0c;也就是典型的单极点响应。相比之下&#xff0c;图…...

npm常用命令使用与事件案例

概述 npm&#xff08;Node Package Manager&#xff09;是一个JavaScript编程语言的包管理器&#xff0c;用于Node.js应用程序。它允许用户安装、共享和管理具有重复使用价值的代码&#xff08;包&#xff09;&#xff0c;这些代码可以是库、工具或应用程序。 npm常用命令详解…...

Spring Boot中的定时任务调度

Spring Boot中的定时任务调度 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们将深入探讨如何在Spring Boot应用中实现定时任务调度&#xff0c;这在实际…...

Hadoop3:MapReduce中的ETL(数据清洗)

一、概念说明 “ETL&#xff0c;是英文Extract-Transform-Load的缩写&#xff0c;用来描述将数据从来源端经过抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;、加载&#xff08;Load&#xff09;至目的端的过程。ETL一词较常用在数据仓库&#…...

python解锁图片相似度的神奇力量

在这个信息爆炸的时代,图片成为了我们传递信息、表达情感和记录生活的重要方式。然而,面对海量的图片资源,如何快速准确地找到相似的图片,成为了一个亟待解决的问题。现在,让我们为您揭开图片相似度的神秘面纱,带您领略这一创新技术的魅力! 图片相似度技术,就像是一位…...

TensorFlow 的原理与使用

文章目录 TensorFlow 的基本原理1. 计算图&#xff08;Computation Graph&#xff09;2. 张量&#xff08;Tensor&#xff09;3. 会话&#xff08;Session&#xff09;4. 自动微分&#xff08;Automatic Differentiation&#xff09; TensorFlow 的使用安装 TensorFlow基本使用…...

[数据库]事务的隔离级别存储引擎

事务的隔离级别 存储引擎 举例 myisam 进行回滚操作后可以发现有一个警告没有行受到影响 memory 比如用于qq的在线离线状态...

使用nvm切换node版本时报错:exit status 1解决办法

作者介绍&#xff1a;计算机专业研究生&#xff0c;现企业打工人&#xff0c;从事Java全栈开发 主要内容&#xff1a;技术学习笔记、Java实战项目、项目问题解决记录、AI、简历模板、简历指导、技术交流、论文交流&#xff08;SCI论文两篇&#xff09; 上点关注下点赞 生活越过…...

Kafka~高吞吐量设计

Kafka 之所以能够实现高性能和高速度&#xff0c;主要归因于以下几个关键因素&#xff1a; 分布式架构&#xff1a;Kafka 采用分布式架构&#xff0c;可以水平扩展&#xff0c;通过增加服务器节点来处理更多的流量和数据存储。顺序写入磁盘&#xff1a;Kafka 将消息顺序地写入…...

STM32小项目———感应垃圾桶

文章目录 前言一、超声波测距1.超声波简介2.超声波测距原理2.超声波测距步骤 二、舵机的控制三、硬件搭建及功能展示总结 前言 一个学习STM32的小白~ 有问题请评论区或私信指出 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、超声波测距 1.超声波…...

嵌入式MCU平台汇总

文章目录 1. 单片机&#xff08;MCU&#xff09; 2. 数字信号处理器&#xff08;DSP&#xff09; 3. ARM Cortex 系列 4. 超低功耗MCU 5. 物联网MCU&#xff08;IoT MCU&#xff09; 6. 开源架构MCU&#xff08;RISC-V&#xff09; 7. 可编程逻辑器件&#xff08;FPGA&a…...

C#udpClient组播

一、0udpClient 控件&#xff1a; button&#xff08;打开&#xff0c;关闭&#xff0c;发送&#xff09;&#xff0c;textbox&#xff0c;richTextBox 打开UDP&#xff1a; UdpClient udp: namespace _01udpClient {public partial class Form1 : Form{public Form1(){Initi…...

《昇思25天学习打卡营第14天 | 昇思MindSpore基于MindNLP+MusicGen生成自己的个性化音乐》

14天 本节学了基于MindNLPMusicGen生成自己的个性化音乐。 MusicGen是来自Meta AI的Jade Copet等人提出的基于单个语言模型的音乐生成模型&#xff0c;能够根据文本描述或音频提示生成高质量的音乐样本。 MusicGen模型基于Transformer结构&#xff0c;可以分解为三个不同的阶段…...

新奥集团校招面试经验分享、测评笔试题型分析

一、走进新奥集团 新奥集团成立于1989年&#xff0c;总部位于河北廊坊&#xff0c;是中国领先的清洁能源企业集团。业务涵盖城市燃气、能源化工、环保科技等多个领域&#xff0c;致力于构建现代能源体系&#xff0c;提升生活品质。 二、新奥集团校招面试经验分享 新奥集团的…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...