AlgoPressAppearance
39-数组中出现次数超过一半的数字
题目描述
https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
- 1 <= 数组长度 <= 50000
注意：本题与主站 169 题相同：https://leetcode.cn/problems/majority-element/
思路：哈希算法
使用字典储存个数，找出最大次数的那个数，复杂度O(n)
csharp
public class Solution {
public int MajorityElement(int[] nums) {
Dictionary<int,int> dict = new Dictionary<int,int>();
int maxCount = 0;
int maxNumber = int.MinValue;
for(int i=0; i<nums.Length; i++){
if(!dict.ContainsKey(nums[i])){
dict.Add(nums[i],1);
}
else{
dict[nums[i]]++;
}
if(dict[nums[i]] > maxCount){
maxCount = dict[nums[i]];
maxNumber = nums[i];
if(maxCount > nums.Length / 2){
return maxNumber;
}
}
}
return maxNumber;
}
}
思路2：投票算法
官方：Boyer-Moore
我们假定设置所有众数为1，其他数为-1，那么将所有的值相加，结果必然大于0，因为众数大于一半的数 我们随机定义一个候选的数为众数(比如第一个)，初始 count = 0，当遇到相同的数就加1，不相同则减1，当 count == 0 的时候，选择当前的数继续为众数，设置count=1，继续 这样遍历完数组之后，最后count一定大于0，而此时的候选数就是众数
csharp
public class Solution {
public int MajorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;
for(int i=1; i<nums.Length; i++){
if(nums[i] == candidate){
count++;
}
else{
count--;
}
if(count == 0){
candidate = nums[i];
count = 1;
}
}
return candidate;
}
}