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

数据结构学习 jz39 数组中出现次数超过一半的数字

关键词:排序 摩尔投票法

摩尔投票法没学过所以没有想到,其他的都自己想。

题目:库存管理 II

方法一:

思路:

排序然后取中间值。因为超过一半所以必定在中间值是我们要的结果。

复杂度计算:

时间复杂度O(nlogn)

空间复杂度O(1)

代码:

class Solution {
public:int inventoryManagement(vector<int>& stock) {if(stock.size()==1) return stock[0];sort(stock.begin(),stock.end());return stock[stock.size()/2];}
};

方法二:

哈希表统计法。

思路:

哈希表统计一遍,如果结果大于一半就返回。

复杂度计算:

时间复杂度O(n)

空间复杂度O(k)数的总类

代码:

class Solution {
public:int inventoryManagement(vector<int>& stock) {if(stock.size()==1) return stock[0];unordered_map<int,int> hash;for(int i=0;i<stock.size();++i){hash[stock[i]]++;if(hash[stock[i]]>stock.size()/2) return stock[i];}return 0;}
};

方法三:最佳解法

 摩尔投票法。

思路:

我是看了k神的题解才会的。建议看。

复杂度计算:

时间复杂度O(n)

空间复杂度O(1)

代码:

class Solution {
public:int inventoryManagement(vector<int>& stock) {int x=0;int votes=0;for(const int&num:stock){if(votes==0) x=num;if(num==x) votes+=1;//和假设的众数x一样,就+1else votes+=-1;//不一样就-1}return x;}
};

相关文章:

数据结构学习 jz39 数组中出现次数超过一半的数字

关键词&#xff1a;排序 摩尔投票法 摩尔投票法没学过所以没有想到&#xff0c;其他的都自己想。 题目&#xff1a;库存管理 II 方法一&#xff1a; 思路&#xff1a; 排序然后取中间值。因为超过一半所以必定在中间值是我们要的结果。 复杂度计算&#xff1a; 时间复杂度…...

基于Linux的Flappy bird游戏开发

项目介绍 主要是使用C语言实现&#xff0c;开启C项目之旅。 复习巩固C语言、培养做项目的思维。 功能&#xff1a; 按下空格键小鸟上升&#xff0c;不按下落&#xff1b; 显示小鸟需要穿过的管道&#xff1b; 小鸟自动向右飞行&#xff1b;&#xff08;管道自动左移和创建&a…...

排序算法6---快速排序(非递归)(C)

回顾递归的快速排序&#xff0c;都是先找到key中间值&#xff0c;然后递归左区间&#xff0c;右区间。 那么是否可以实现非递归的快排呢&#xff1f;答案是对的&#xff0c;这里需要借助数据结构的栈。将右区间左区间压栈&#xff08;后进先出&#xff09;&#xff0c;然后取出…...

【Verilog】期末复习——设计带异步清零且高电平有效的4位循环移位寄存器

系列文章 数值&#xff08;整数&#xff0c;实数&#xff0c;字符串&#xff09;与数据类型&#xff08;wire、reg、mem、parameter&#xff09; 运算符 数据流建模 行为级建模 结构化建模 组合电路的设计和时序电路的设计 有限状态机的定义和分类 期末复习——数字逻辑电路分…...

银行网络安全实战对抗体系建设实践

文章目录 前言一、传统攻防演练面临的瓶颈与挑战&#xff08;一&#xff09;银行成熟的网络安全防护体系1、缺少金融特色的演练场景设计2、资产测绘手段与防护体系不适配3、效果评价体系缺少演练过程维度相关指标 二、实战对抗体系建设的创新实践&#xff08;一&#xff09;建立…...

SwiftUI之深入解析Alignment Guides的超实用实战教程

一、Alignment Guide 简介 Alignment guides 是一个强大的布局工具&#xff0c;但通常未被充分利用。在很多情况下&#xff0c;它们可以帮助我们避免更复杂的选项&#xff0c;比如锚点偏好。如下所示&#xff0c;对对齐的更改也可以自动&#xff08;并且容易地&#xff09;动画…...

java获取视频文件的编解码器

java获取视频文件的编解码器 引入jar包&#xff1a; <dependency><groupId>org.bytedeco</groupId><artifactId>javacv-platform</artifactId><version>1.5.9</version></dependency>测试类 package com.jd.brand.approve.…...

动态规划Day06(完全背包)

完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同…...

selenium之框架之窗口

...

华为OD机试 - 最小矩阵宽度(Java JS Python C)

题目描述 给定一个矩阵,包含 N * M 个整数,和一个包含 K 个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子矩阵,要求子矩阵包含数组中所有的整数。 输入描述 第一行输入两个正整数 N,M,表示矩阵大小。 接下来 N 行 M 列表示矩阵内容。 下一行包含一个正整数 K…...

嵌入式linux_C应用学习之API函数

1.文件IO 1.1 open打开文件 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode);pathname&#xff1a;字符串类型&#xff0c;用于标…...

【ubuntu】docker中如何ping其他ip或外网

docker中如何ping其他ip或外网 示例图&#xff1a; 运行下面命令&#xff1a; docker run -it --namehei busybox看情况需要加权限 sudo&#xff0c;即&#xff1a; sudo docker run -it --namehei busyboxping 外网 ping -c 4 www.baidu.comping 内网 ping -c 4 192.168.…...

【Vue3+Ts项目】硅谷甄选 — 品牌管理+平台属性管理+SPU管理+SKU管理

一、品牌管理模块 1.1 静态模块搭建 使用到element-plus的card、button、table、pagination等组件&#xff1a;src/views/product/trademark/index.vue <template><el-card><!-- 卡片顶部添加品牌按钮 --><el-button type"primary" size&quo…...

计算机图形学流体模拟 blender 渲染脚本

做流体模拟的时候&#xff0c;想要复现别人的成果&#xff0c;但是别人的代码都是每帧输出 ply 格式的文件&#xff0c;渲染部分需要自己完成 看了一下&#xff0c;似乎用 blender 是最简单的&#xff0c;于是记录一下过程中用到的代码 Blender 版本 4.0 批量导入 ply 假设…...

二分图带权最大匹配-KM算法详解

文章目录 零、前言一、红娘再牵线二、二分图带权最大完备匹配2.1二分图带权最大匹配2.2概念2.3KM算法2.3.1交错树2.3.2顶标2.3.3相等子图2.3.4算法原理2.3.5算法实现 三、OJ练习3.1奔小康赚大钱3.2Ants 零、前言 关于二分图&#xff1a;二分图及染色法判定-CSDN博客 关于二分…...

Redis命令 - Sets命令组常用命令

Set集合&#xff0c;无序&#xff0c;一堆不重复值的组合。利用redis提供的set数据结构&#xff0c;可以存储一些集合性的数据。 使用场景&#xff1a;例如&#xff0c;实现如共同关注、共同喜好、二度好友等 1、SADD key member [member …] 向集合中添加一个或者多个成员 …...

DA14531-外设驱动篇-I2C通信应用

文章目录 1.I2C通信应用相关文件2.宏定义列表3.主要函数接口4.应用代码实例1.I2C通信应用相关文件 1)i2c.c和i2c.h(SDK文件) 2)app_I2cProtocol.c和app_I2cProtocol.h(用户应用文件) 2.宏定义列表 宏定义注解I2C_ADDRESSING_7B7-bit 地址I2C_ADDRESSING_10B10-bit 地址…...

Git仓库管理笔记

问题&#xff1a; hint: the same ref. If you want to integrate the remote changes, use Done 解决&#xff1a; 解决方法&#xff1a; 1、先使用pull命令&#xff1a; git pull --rebase origin master 2、再使用push命令&#xff1a; git push -u origin master...

[嵌入式软件][入门篇] 搭建在线仿真平台(STM32)

文章目录 一、注册平台二、创建首个项目三、硬件介绍 一、注册平台 进入官方&#xff0c;进行注册&#xff1a; 在线仿真地址 二、创建首个项目 ① 新建项目 ② 搭建一个电路 ③ 用STM32F103搭建一个简单电路 ④ 进入编码界面 三、硬件介绍 红框是必看文档&#xff…...

设置5台SSH互免的虚拟机服务器配置

搭建一套集群虚拟机&#xff0c;往往都需要互免设置&#xff0c;过程很简单&#xff0c;避免以后再搭建还得网上搜索&#xff0c;我直接将这一个步骤写成笔记&#xff0c;记录下来&#xff0c;方便后续查阅。 步骤如下—— 1、准备五台机器 服务器名字服务器IPhadoop1192.16…...

深信服技术认证“SCCA-C”划重点:交付和运维体系

为帮助大家更加系统化地学习云计算知识&#xff0c;高效通过云计算工程师认证&#xff0c;深信服特推出“SCCA-C认证备考秘笈”&#xff0c;共十期内容。“考试重点”内容框架&#xff0c;帮助大家快速get重点知识。 划重点来啦 *点击图片放大展示 深信服云计算认证&#xff…...

xlua源码分析(五) struct类型优化

xlua源码分析&#xff08;五&#xff09; struct类型优化 上一节我们分析了xlua是如何实现lua层访问C#值类型的&#xff0c;其中我们重点提到了xlua默认实现方式下&#xff0c;struct访问的效率问题。实际上&#xff0c;xlua还提供了两种优化的方式&#xff0c;可以大大提高str…...

iptables TEE模块测试小记

概述 因为公司项目需求&#xff0c;需要对服务器特定端口进行流量镜像&#xff0c;各种百度之后&#xff0c;发现TEE的模块&#xff0c;后来一番折腾&#xff0c;发现被转发的机器死活收不到数据&#xff0c;最后tcpdump一通了解到根源&#xff0c;博文记录&#xff0c;用以备…...

[IDE]vscode显示文件路径

...

facebook广告怎么设置受众人群

在设置Facebook广告受众人群时&#xff0c;你可以遵循以下步骤&#xff1a; 打开广告创建工具&#xff0c;点击页面右上角的箭头并选择“创建广告”。选择广告目标&#xff0c;根据想要实现的目标创建广告。例如&#xff0c;想要让更多用户谈论你的主页和帖子&#xff0c;或者…...

MySQL夯实之路-MVCC机制深入浅出

多版本并发控制&#xff08;MVCC&#xff0c;multiversion concurrency control&#xff09; MVCC用更加灵活的方式处理并发&#xff0c;实现了读不加锁&#xff0c;读写不冲突。保证了事务的隔离性&#xff08;可重复读&#xff09;&#xff0c;避免了不可重复读问题。 数据…...

Java线上问题堆栈排查分析

最近线上出现类似内存溢出问题&#xff0c;需要排查具体原因&#xff0c;记录过程&#xff0c;方便备查。 一、数据抓取 在启动参数中添加参数&#xff0c;可参照以下设置。 参数的作用是在程序发生内存溢出 OutOfMemory 时打印日志&#xff0c;dump下来&#xff0c;方便用工…...

C语言代码 计算1!+2!+3!+4!+5!+6!+7!+8!+9!+10!

计算1!2!3!4!5!6!7!8!9!10! 代码示例&#xff1a; #include <stdio.h> int main() {int i 0;int n 0;int ret 1;int sum 0;for (n 1; n < 10; n){ret 1;for (i 1; i < n; i){ret ret * i;}sum sum ret;}printf("%d\n", sum);return 0; } 运…...

【RTOS】快速体验FreeRTOS所有常用API(4)队列

目录 四、队列2.1 概念2.2 创建队列2.3 写队列2.4 读队列2.5 队列集&#xff08;可跳过&#xff09; 四、队列 该部分在上份代码基础上修改得来&#xff0c;代码下载链接&#xff1a; https://wwzr.lanzout.com/iBNAS1l75bvc 密码:7xy2 该代码尽量做到最简&#xff0c;不添加多…...

【开题报告】基于SpringBoot的美食制作学习网站的设计设计与实现

1.选题背景 随着人们生活水平的提高&#xff0c;对美食的追求也越来越高。越来越多的人希望能够在家里制作出各种美味的菜肴。然而&#xff0c;对于许多人来说&#xff0c;缺乏专业的指导和实践经验是一个挑战。另外&#xff0c;互联网的普及与发展&#xff0c;为人们提供了更…...

当铺网站建设方案/小程序引流推广平台

https://jingyan.baidu.com/article/e4d08ffdf7b8454ed2f60da2.html...

海宁网站设计公司/南京网站建设

补题链接&#xff1a; https://acm.hdu.edu.cn/showproblem.php?pid7059 考点: 线段树 解题思路可参考&#xff1a;https://www.cnblogs.com/lipoicyclic/p/15139116.html 但是与下面的代码不同的是: 下面代码考虑的是flag true 代表[l, r]区间内ai为0&#xff0c;即高位和…...

银川网站建设哪家好/有哪些平台可以做推广

此文转载自&#xff1a;https://my.oschina.net/u/4701816/blog/4705244大咖揭秘Java人都栽在了哪&#xff1f;点击免费领取《大厂面试清单》&#xff0c;攻克面试难关~>>>Rust 包管理器 Cargo 入门 了解 Rust 的软件包管理器和构建工具。 -- Gaurav Kamathe(作者) Ru…...

做班级相册网站的目的意义/chrome浏览器下载安卓手机

Author&#xff1a;TrulyJSON定义 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式&#xff0c;易于阅读和编写&#xff0c;同时也易于机器解析和生成。它基于ECMA262语言规范&#xff08;1999-12第三版&#xff09;中JavaScript编程语言的一个子集。 JSON采用…...

地方门户网站建设/宣传推广方式有哪些

这是一个快节奏的时代&#xff0c;工作时讲究高效率&#xff0c;打游戏刷剧时网速越快越好&#xff0c;“从前的日色变得慢&#xff0c;车&#xff0c;马&#xff0c;邮件都慢”听起来十分的美好&#xff0c;但是在当下社会&#xff0c;如果交通工具、沟通方式失去了快这个优点…...

flash做的小动画视频网站/邹平县seo网页优化外包

删除or输出链表倒数的第k个元素 题目描述 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 进阶&#xff1a;你能尝试使用一趟扫描实现吗&#xff1f; 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1…...