技术标签： 算法设计与分析
有一个数组，里面是一些重复的数字。问是否存在一个数，这个数出现的次数超过了数组大小的一半？如果存在的话，这个数是多少？
例如对于数组[1,1,3,1,3,1,2]，数字1的出现的次数超过了数组的一半；
而对于数组[6,6,6,7,7,7]，没有数字超过数组的一半（数字6和7都出现了3次，出现的次数等于数组的一半，而没有超过数组的一半）
如果题目要求的是数字出现的次数大于等于数组的一半，那多数投票算法就失效了，只能用其他方法来实现。
对于这个问题，最佳的算法是多数投票算法，也叫作Boyer-Moore algorithm。
对这个问题，最大投票算法的时间复杂度是O(n)（总共遍历两次数组），空间复杂度是O(1)（总共维护两个变量）
算法的思想是，如果一个数存在超过数组的一半，则这个数和其他数相互抵消，最终还是会有自己的同党剩下来。
例如有一些人来投票，投的票选项分别是[1,3,2,1,1].
第一个人投1号，第二个人投3号，两个选票不同，相互抵消；
第三个人投2号，第四个人投1号，两个选票不同，相互抵消；
最后剩下一个1号投票，1号也是超过半数的投票号。
再看一个例子：[1,1,3,4,2]
第1、2个人的投票将选项1的票数累加到2；
第3、4个人的投票不是1，所以抵消选项1的票数到0；
最后一个人的投票是2.
但是很明显，2号不是多数的票号。所以我们需要再遍历一次数组来判断2号票是不是多数票。这个就是多数投票算法的思想。
public int majorityVote(int nums[]) {
int candidate=0,count=0;
for(Integer num : nums) {
if(num==candidate) {
count++;
}else if(count==0) {
candidate=num;
count=1;
}else {
count--;
}
}
count=0;
for(Integer num : nums)
if(num==candidate) count++;
if(count>Math.ceil(nums.length/2)) return candidate;
return -1; // 表示没有超过半数的票
}
传进函数的参数nums数组表示选票的票号，candidate表示可能的多数票号，初始值就设为0，count可以粗略理解为多数票号超过了其他票号的票数有多少。
leetcode 229中求的就是超过三分之一的选票。
可以轻易想到，超过数组三分之一长度的数最多有两个，不可能有三个。
例如[1,1,1,2,2,2,3,3,3]就不存在超过数组三分之一长度的数字
而数组[1,1,1,2,2,2,3,3]存在两个超过数组三分之一长度的数字1、2
做法类似.
文章浏览阅读2.3k次。很简单，看图：_tableau更换筛选器后怎么添加到汇总表里
文章浏览阅读4.7k次，点赞3次，收藏8次。pip更新安装包的时候出现错误，如下图所示：解决方法是：pip install --user [要安装的包] #加上一个–user就好了_pip23.3.2安装包时拒绝访问
文章浏览阅读331次。题目链接：题目腾讯游戏开发了一款全新的编程类益智小游戏，最新推出的一个小游戏题目是关于矩形面积交的。聪明的你能解出来吗？看下面的题目接招吧。给定二维平面上 nnn 个与坐标轴平行的矩形，每个矩形是形如 {(x,y)∣x,y∈R,x1≤x≤x2,y1≤y≤y2}\lbrace (x,y) | x,y \in R, x_1 \le x \le x_2, y_1 \le y \le y_2 \rbrace{(x,y)∣x,y∈R,x1≤x≤x2,y1≤y≤y2} 的点集，你的任务是对于每个矩形，计算它与_游戏两矩形相交计算
文章浏览阅读733次，点赞16次，收藏16次。免费领取项目源码，请关注●点赞收藏并私信博主，谢谢~宠物店管理系统主要功能模块包括宠物类型、宠物医生、普通挂号、会员挂号、宠物护理、护理订单、提醒信息、会员提醒、护理订单（会员）等信息维护，采取面对对象的开发模式进行软件的开发和硬体的架设，能很好的满足实际使用的需求，完善了对应的软体架设以及程序编码的工作，采取MySQL作为后台数据的主要存储单元，采用Java技术、Ajax技术进行业务系统的编码及其开发，实现了本系统的全部功能。本次报告，首先分析了研究的背景、作用、意义，为研究工作的合理性打下了基础。针对
文章浏览阅读271次。在R语言中，我们可以使用ggplot2包来创建漂亮的柱状图，并且可以自定义每个柱子的填充颜色。在本例中，我们将使用mtcars数据集，该数据集包含了不同汽车型号的性能指标。通过使用fill参数，我们可以轻松地为柱状图指定填充颜色，以增强数据可视化效果。你可以根据自己的需要选择不同的颜色方案，或者根据数据的特点来选择合适的填充颜色。现在我们可以使用ggplot函数创建柱状图，并使用fill参数指定填充颜色。每个柱子将使用不同的颜色进行填充，颜色的顺序与数据中汽车品牌的顺序相对应。在这个例子中，我们使用了。_如果对柱状图进行颜色润色的话,需要用到下面 哪一个参数?
文章浏览阅读534次，点赞9次，收藏10次。分时系统允许多个用户同时使用一台计算机，为了保证系统的安全和记帐方便，系统要求每个用户有单独的帐号作为登录标识，系统还为每个用户指定了一个口令。用户在使用该系统之前要输入标识和口令，这个过程被称为’登远程登陆是指用户使用Telnet命令，使自己的计算机暂时成为远程主机的一个仿真终端的过程。但是，telnet因为采用明文传送报文，安全性不好，很多Linux服务器都不开放telnet服务，而改用更安全的ssh方式了。因为默认是不允许root登陆的，我没有去开启允许root直接登陆，所以我用的一个普通用户登陆！
文章浏览阅读5.4k次，点赞2次，收藏11次。HTML嵌入JavaScript代码的三种方式_24、在html中,可以引入javascrint代码方式(3分)是()。a、a、行内式b、b、内嵌
文章浏览阅读6w次，点赞73次，收藏50次。问题打开调试器，F5刷新页面后出现下面这种情况没有出现资源等想要的信息(注：从参考1里面得到如下图）解决方法1、打开Edge浏览器里面的调试器的设置2、重置默认并刷新即可注：chrome浏览器的开发者工具的设置也在类似位置参考1、edge等浏览器打开开发者工具（F12）之后在NetWork看不到请求头等信息..._浏览器开发者工具 console没有请求信息
文章浏览阅读953次。1, 调试前肩后肩的驱动，那个文件是那个设备的驱动？，lcd刷新频率。2，MMC sdiosd驱动框架看下；大概了解记忆sdio协议。复读一下wifi驱动的框架，3，i2c驱动框架。4，Makefile基本常识基本语句 1，解决过什么问题：收货什么经验，自己的review的总结： 1，解决当wifi没有连接到路由器上时，此时通过_adv7280a移植
文章浏览阅读875次。1.asp.net webform用“Request.PhysicalApplicationPath获取站点所在虚拟目录的物理路径，最后包含“\”；2.c# winform用A：“Application.StartupPath”:获取当前应用程序所在目录的路径，最后不包含“\”；B：“Application.ExecutablePath ”:获取当前应用程序文件的路径，包含文件_c获取当前程序的路径
文章浏览阅读233次。分布式事务解决方案-TCC什么是TCC事务TCC是Try、Confirm、Cancel三个词的缩写，TCC要求每个分支事务实现三个操作，预处理Try、确认Confirm、撤销Cancel。Try操作做业务检查及资源预留，Confirm做业务确认操作，Cancel实现一个与Try相反得cao操作的回滚操作。TM首先先发起所有的分支事务的try操作，任何一个分支事务的Try操作执行失败，TM将会发起所有的分支事务的Cancel操作，若Try操作全部成功,TM将会发起所有分支事务的Confirm操作，其中Co
文章浏览阅读3.2k次。不管你是一位高级工程师还是程序小白，想要创建一个 ChatGPT 驱动的应用并将其部署到生产环境中，那你一定不要错过官方 ChatGPT 生产最佳实践指南，它将使从头开始构建一个高质量的AI产品变得轻而易举。_open ai chatgpt继续生成和停止生成接口