LeetCode刷题（63）～多数元素【哈希/排序/随机/Boyer-Moore 投票算法/分治 ！！！】

题目描述

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

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

示例 1:

输入: [3,2,3]
输出: 3

  

 

  
1
  
2
 

示例 2:

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

  

 

  
1
  
2
 

解答 By 海轰

提交代码（哈希）

int majorityElement(vector<int>& nums) { int len=nums.size(); unordered_map<int,int> m; for(int i=0;i<len;++i) { ++m[nums[i]]; if(m[nums[i]]>len/2) return nums[i]; } return 0; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

运行结果

提交代码（排序，寻找第n/2个元素）

int majorityElement(vector<int>& nums) { sort(nums.begin(),nums.end()); return nums[nums.size()/2]; }

  

 

  
1
  
2
  
3
  
4
 

运行结果

提交代码（随机）

int majorityElement(vector<int>& nums) { while (true) { int candidate = nums[rand() % nums.size()]; int count = 0; for (int num : nums) if (num == candidate) ++count; if (count > nums.size() / 2) return candidate; } return -1; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

运行结果

提交代码（Boyer-Moore 投票算法）

int majorityElement(vector<int>& nums) { int a=0; int count=0; for(int num:nums) { if(a==num) { ++count; } else if(--count<0) { a=num; count=1; } } return a; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

思路详解😆

题目来源

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

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

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