LeetCode刷题（156）～主要元素【摩尔投票法】

题目描述

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

  

 

  
1
  
2
 

示例 2：

输入：[3,2]
输出：-1

  

 

  
1
  
2
 

示例 3：

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

  

 

  
1
  
2
 

说明：

• 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

解答 By 海轰

提交代码（哈希）

int majorityElement(vector<int>& nums) { unordered_map<int,int> m; for(int num:nums) { ++m[num]; if(m[num]>nums.size()/2) return num; } return -1; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

运行结果

提交代码（摩尔投票法）

int majorityElement(vector<int>& nums) { int count=0; int major; for(int num:nums) { if(count==0) { major=num; ++count; } else { if(num==major) ++count; else --count; } } if(count>0) { int s=0; for(int num:nums) { if(num==major) ++s; if(s>nums.size()/2) return num; } } return -1; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-majority-element-lcci

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108592487