网站的动态新闻数据库怎么做,石家庄智能模板建站,wordpress自定义侧边栏,口碑好的南昌网站建设leetcode_169. 多数元素
问题描述
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a;
输入#xff1a;nums …leetcode_169. 多数元素
问题描述
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109
**进阶**尝试设计时间复杂度为 O ( n ) O(n) O(n)、空间复杂度为 O ( 1 ) O(1) O(1)的算法解决此问题。
题解-Boyer-Moore 投票算法
做这到题我们要紧扣两点, res(结果)一定是数组中最多的, 而且比其他任何数都多!!!
牢记上面的话, 然后我们来看算法
如果一场竞选中, 我们有 n n n个候选人, 每个候选人都会有自己的支持者, 对于第 i i i个候选人($ 0in ) 他们都有 )他们都有 )他们都有arr[i]$个支持者, 在竞选中, 每个支持者可以为自己支持的候选人投支持票, 同样也可以为自己不支持的候选人投反对票(每个人都只能有一个支持的候选人, 且每个人都能投一次票, 无论是支持还是反对). 这时, 有一个天降猛男**“甲”, 支持者超过了 50 % 50\% 50%, 那么请问, 如果其他候选者联合起来给甲捣乱, 比如某几个候选人串通, 让他们的支持者去给甲**投反对票, 或者把票都投给某一个甲以外的候选者, 能不能对竞选结果产生影响呢?
显然不能, 因为甲的支持者是超过 50 % 50\% 50%的, 哪怕就超过一个人也是一样, 甲是 100 % 100\% 100% 会赢的, 无论其他人怎么操作. 就算剩下的所有的候选人支持者都把票投给一个人, 也不会超过甲.
在上面那个例子里, 甲就是我们的多数元素, 甲的支持者的数量就是多数元素出现的次数,
为了实现上面的算法, 我们需要维护两个变量, 一个res记录候选的多数元素和它出现的次数count, 一开始count为0, res记录数组的第一个元素, 随后每当遇到一个与当前res相同的 就执行count, 否则就count--, 当count0时, 就改变res的值为当前遍历的值,
这样一来, 无论数组里的元素顺序如何, 最后res里的值都会是我们的多数元素,
如果遍历到我们的多数元素时res中记录的正好是这个值, 那么count, 就想当与支持者给自己投了支持票, 如果遍历到多数元素时, res中记录的是别的数字, 那么count--, 就相当于自己的支持者给别人投了反对票, 不管怎么样, 多数元素的票的总量多余其他所有元素之和, 所以最后res的值一定就是我们的多数元素.
java
class Solution {public int majorityElement(int[] nums) {int res -1, count 0;for (int num : nums) {if (count 0) {res num;count 1;} else if (res num ) {count ;} else {count --;}}return res;}
}C
class Solution {
public:int majorityElement(vectorint nums) {int res -1, count 0;for (int num : nums) {if (count 0) {res num;count 1;} else if (res num ) {count ;} else {count --;}}return res;}
};
