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

【practise】数组中出现次数超过一半的数字

news 来源：原创 2024/9/19 12:43:28

关于我： 在这里插入图片描述

睡觉待开机：个人主页

个人专栏: 《优选算法》《C语言》《CPP》 生活的理想，就是为了理想的生活! 作者留言

PDF版免费提供：倘若有需要，想拿我写的博客进行学习和交流，可以私信我将免费提供PDF版。
留下你的建议：倘若你发现本文中的内容和配图有任何错误或改进建议，请直接评论或者私信。
倡导提问与交流：关于本文任何不明之处，请及时评论和私信，看到即回复。

参考目录

1.前言
2.题目简介
3.题目思路
4.参考代码

1.前言

今天我们来简单分享一道不同于经典双指针啊，前缀和算法…等等很有体系的题目，咱们来一道不难，但是思路却比较新颖的题目。
我想，如果你没有接触过这类题目还真不见得可以想到这种方法——投票选举。

2.题目简介

题目链接：LINK
在这里插入图片描述
题意：题目叙述很简单，给你一个数组，让你找出其中出现次数超过一半的一个元素。

不知你是否想到了什么思路，我立刻想到的就是用哈希数组进行一一记数然后遍历哈希数组找到出现次数超过一半的那个元素。
但是显然这种解法不满足题目要求，空间复杂度是O(N)级别的，我们题目要求是O(1)

这里空间复杂度的限制，这样就很难了。

3.题目思路

加入数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

具体做法：
初始化：候选人cond = -1，候选人的投票次数cnt = 0
遍历数组，如果cnt=0，表示没有候选人，则选取当前数为候选人，++cnt
否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则–cnt
直到数组遍历完毕，最后检查cond是否为众数

这是什么原理呢？下面我来为大家举例解读。
是这样的，有很多人投票，每个人都对自己心仪的对象进行投票，最后的结果肯定是谁的投票高谁得第一。假设现在有一个计票员，需要依次对每个人手里的票进行记录，比赛结果要求很简单，不用按票数排名，只需要知道第一名是谁就行了，对第二名第三名…并不关注。
在这里插入图片描述
现在，我们把vector中的元素看作一个一个的投票人，每个元素的数值就是对应的投票对象。而我们的计票员依次对每个人计票就是类似于我们一个变量依次遍历数组。

这时候，计票员只需要准备两个变量，一个变量存放当前是谁第一，第二个变量是存放相比于其他人第一名的相对票数。
我们知道，数组中出现次数超过一半的数字势必会比其他人所有出现次数之和都多。
在这里插入图片描述

4.参考代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int MoreThanHalfNum_Solution(vector<int>& numbers) {// write code hereint count = 0;int candidate = -1;for(int i = 0; i < numbers.size(); i++){if(count == 0){candidate = numbers[i];count++;}else {if(numbers[i] == candidate){count++;}else {count--;}}}return candidate;}
};