169. 多数元素【 力扣(LeetCode) 】
一、题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
二、测试用例
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
三、解题思路
- 基本思路：题目保证数组非空且一定存在多数元素，则可以考虑打擂台；
- 具体思路：先确定擂主 x ，初始化为数组第一个元素，再确定擂主血量 count ，初始化为 1 。接下来遍历序列，每遇到一个元素，判断是否和擂主相同，相同表示朋友，擂主血量 count + 1 ；不同表示敌人，擂主血量 count - 1 ；一旦擂主血量归 0 ，表示守擂失败，则新元素成为擂主，血量置为 1 ，继续守擂，直到遍历结束，擂主就是多数元素。【不同元素相互抵消，如果抵消的多数元素，则多数元素血量还是最高的，如果相互抵消的不是多数元素，则多数元素血量还是最高的】
四、参考代码
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
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;
}
测试结果：
原文地址：https://blog.csdn.net/yyh520025/article/details/140686325
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！