169. 多数元素【 力扣(LeetCode) 】

一、题目描述

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

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

二、测试用例

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

三、解题思路

1. 基本思路：题目保证数组非空且一定存在多数元素，则可以考虑打擂台；
2. 具体思路：先确定擂主 x ，初始化为数组第一个元素，再确定擂主血量 count ，初始化为 1 。接下来遍历序列，每遇到一个元素，判断是否和擂主相同，相同表示朋友，擂主血量 count + 1 ；不同表示敌人，擂主血量 count - 1 ；一旦擂主血量归 0 ，表示守擂失败，则新元素成为擂主，血量置为 1 ，继续守擂，直到遍历结束，擂主就是多数元素。【不同元素相互抵消，如果抵消的多数元素，则多数元素血量还是最高的，如果相互抵消的不是多数元素，则多数元素血量还是最高的】

四、参考代码

时间复杂度：$O(n)$
空间复杂度：$O(1)$

int majorityElement(vector<int>& nums) {int x=nums[0],count=1,n=nums.size();for(int i=1;i<n;i++){if(x==nums[i]){count++;}else{count--;if(count==0){x=nums[i];count=1;}}}return x;
}

测试结果：