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 ,请你返回其中出现频率前 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. 封装 封装的意义 将属性和行为作为一个整体,表现生活中的事物;将属性和行为加以权限控制 public -> 公共权限:类内可以访问,类外也可以访问protected -> 保护权限:类内可以访问,…...
基于PHP的初中数学题库管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的初中数学题库管理系统 一 介绍 此初中数学题库管理系统基于原生PHP开发,数据库mysql,系统角色分为学生,教师和管理员。(附带参考设计文档) 技术栈:phpmysqlphpstudyvscode 二 功能 …...
WDG看门狗
1 WDG 1.1 简介 WDG是看门狗定时器(Watchdog Timer)的缩写,它是一种用于计算机和嵌入式系统中的定时器,用来检测和恢复系统故障。 看门狗就像是一个忠诚的宠物狗,它时刻盯着你的程序,确保它们正常运行。…...
zabbix server client 安装配置
Zabbix Server 采用源码包部署,数据库采用 MySQL8.0 版本,zabbix-web 使用 nginxphp 来实现。具体信息如下: 软件名 版本 安装方式 Zabbix Server 6.0.3 源码安装 Zabbix Agent 6.0.3 源码安装 MySQL 8.0.28 yum安装 Nginx 1.20…...
Unity关于Addressables.Release释放资源内存问题
前言 最近在编写基于Addressables的资源管理器,对于资源释放模块配合MemoryProfiler进行了测试,下面总结下测试Addressables.Release的结论。 总结 使用Addressables.Release释放资源时,通过MemoryProfiler检查内存信息发现加载的内容还在…...
运算放大器(运放)带宽和带宽平坦度
运算放大器带宽和带宽平坦度 电压反馈型运算放大器的带宽 下图1显示电压反馈型运算放大器的开环频率响应。有两种可能:图1A是最常见的情况,高直流增益以6dB/倍频程从极低频率下降至单位增益,也就是典型的单极点响应。相比之下,图…...
npm常用命令使用与事件案例
概述 npm(Node Package Manager)是一个JavaScript编程语言的包管理器,用于Node.js应用程序。它允许用户安装、共享和管理具有重复使用价值的代码(包),这些代码可以是库、工具或应用程序。 npm常用命令详解…...
Spring Boot中的定时任务调度
Spring Boot中的定时任务调度 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将深入探讨如何在Spring Boot应用中实现定时任务调度,这在实际…...
Hadoop3:MapReduce中的ETL(数据清洗)
一、概念说明 “ETL,是英文Extract-Transform-Load的缩写,用来描述将数据从来源端经过抽取(Extract)、转换(Transform)、加载(Load)至目的端的过程。ETL一词较常用在数据仓库&#…...
python解锁图片相似度的神奇力量
在这个信息爆炸的时代,图片成为了我们传递信息、表达情感和记录生活的重要方式。然而,面对海量的图片资源,如何快速准确地找到相似的图片,成为了一个亟待解决的问题。现在,让我们为您揭开图片相似度的神秘面纱,带您领略这一创新技术的魅力! 图片相似度技术,就像是一位…...
TensorFlow 的原理与使用
文章目录 TensorFlow 的基本原理1. 计算图(Computation Graph)2. 张量(Tensor)3. 会话(Session)4. 自动微分(Automatic Differentiation) TensorFlow 的使用安装 TensorFlow基本使用…...
[数据库]事务的隔离级别存储引擎
事务的隔离级别 存储引擎 举例 myisam 进行回滚操作后可以发现有一个警告没有行受到影响 memory 比如用于qq的在线离线状态...
使用nvm切换node版本时报错:exit status 1解决办法
作者介绍:计算机专业研究生,现企业打工人,从事Java全栈开发 主要内容:技术学习笔记、Java实战项目、项目问题解决记录、AI、简历模板、简历指导、技术交流、论文交流(SCI论文两篇) 上点关注下点赞 生活越过…...
Kafka~高吞吐量设计
Kafka 之所以能够实现高性能和高速度,主要归因于以下几个关键因素: 分布式架构:Kafka 采用分布式架构,可以水平扩展,通过增加服务器节点来处理更多的流量和数据存储。顺序写入磁盘:Kafka 将消息顺序地写入…...
STM32小项目———感应垃圾桶
文章目录 前言一、超声波测距1.超声波简介2.超声波测距原理2.超声波测距步骤 二、舵机的控制三、硬件搭建及功能展示总结 前言 一个学习STM32的小白~ 有问题请评论区或私信指出 提示:以下是本篇文章正文内容,下面案例可供参考 一、超声波测距 1.超声波…...
嵌入式MCU平台汇总
文章目录 1. 单片机(MCU) 2. 数字信号处理器(DSP) 3. ARM Cortex 系列 4. 超低功耗MCU 5. 物联网MCU(IoT MCU) 6. 开源架构MCU(RISC-V) 7. 可编程逻辑器件(FPGA&a…...
C#udpClient组播
一、0udpClient 控件: button(打开,关闭,发送),textbox,richTextBox 打开UDP: UdpClient udp: namespace _01udpClient {public partial class Form1 : Form{public Form1(){Initi…...
《昇思25天学习打卡营第14天 | 昇思MindSpore基于MindNLP+MusicGen生成自己的个性化音乐》
14天 本节学了基于MindNLPMusicGen生成自己的个性化音乐。 MusicGen是来自Meta AI的Jade Copet等人提出的基于单个语言模型的音乐生成模型,能够根据文本描述或音频提示生成高质量的音乐样本。 MusicGen模型基于Transformer结构,可以分解为三个不同的阶段…...
新奥集团校招面试经验分享、测评笔试题型分析
一、走进新奥集团 新奥集团成立于1989年,总部位于河北廊坊,是中国领先的清洁能源企业集团。业务涵盖城市燃气、能源化工、环保科技等多个领域,致力于构建现代能源体系,提升生活品质。 二、新奥集团校招面试经验分享 新奥集团的…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...
Shell 解释器 bash 和 dash 区别
bash 和 dash 都是 Unix/Linux 系统中的 Shell 解释器,但它们在功能、语法和性能上有显著区别。以下是它们的详细对比: 1. 基本区别 特性bash (Bourne-Again SHell)dash (Debian Almquist SHell)来源G…...
PostgreSQL 对 IPv6 的支持情况
PostgreSQL 对 IPv6 的支持情况 PostgreSQL 全面支持 IPv6 网络协议,包括连接、存储和操作 IPv6 地址。以下是详细说明: 一、网络连接支持 1. 监听 IPv6 连接 在 postgresql.conf 中配置: listen_addresses 0.0.0.0,:: # 监听所有IPv4…...
