力扣 hot100 Day64

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:int majorityElement(vector<int>& nums) {int count = 0;int candidate = nums[0];for (int num : nums) {if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;}return candidate;}
};

摩尔投票法

维护一个候选数及其获票数，从头开始计票，相同加一，不同减一，票数清零则从下一个数继续计票

非目标数肯定不能留到最后，因为前面消耗的目标数最多一半，所以后面至少也还有过半的目标数，所以最后留下的一定是目标数