Problem: 169. 多数元素
目录思路
这里选择采用摩尔投票的方式进行计算众数,这里众数的定义是超过一半的数, 假设众数的票为+1, 负数的票为-1, 则不难得到:
- 当目前的票数为0时, 后面的众数仍然是整个数组的众数. 根据这个性质设计算法
- 所有数的票面值和为正数
解题方法
初始化众数为nums[0], vote=0, 计算票面值和, 如果vote=0则将众数更新为后一个
复杂度
时间复杂度:
\(O(n)\)
空间复杂度:
\(O(1)\)
Code
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n=nums.size();
int count=n/2;
int vote=0,x=nums[0];
for (size_t i = 0; i < n; i++)
{
if(nums[i]==x) vote++;
else vote--;
if(vote==0) x=nums[i+1];
}
return x;
}
};
标签:nums,int,复杂度,摩尔,169,众数,vote,leetcode
From: https://www.cnblogs.com/oxidationreaction/p/17976212