# C#LeetCode刷题之#169-求众数（Majority Element）

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

Input: [3,2,3]

Output: 3

Input: [2,2,1,1,1,2,2]

Output:

```public class Program {

public static void Main(string[] args) {
int[] nums = { 2, 2, 1, 1, 1, 2, 2 };

var res = MajorityElement(nums);
Console.WriteLine(\$"{res}");

res = MajorityElement2(nums);
Console.WriteLine(\$"{res}");

res = MajorityElement3(nums);
Console.WriteLine(\$"{res}");

}

private static int MajorityElement(int[] nums) {
//哈希法
var dic = new Dictionary<int, int>();
int maxCount = nums.Length / 2;
for(int i = 0; i < nums.Length; i++) {
if(dic.ContainsKey(nums[i])) {
dic[nums[i]]++;
} else {
dic[nums[i]] = 1;
}
if(dic[nums[i]] > maxCount) {
return nums[i];
}
}
return -1;
}

private static int MajorityElement2(int[] nums) {
int result = 0;
for(int i = 0, count = 0; i < nums.Length; i++) {
if(count == 0 || result == nums[i]) {
//当计数为0时，重置计数和结果
//当上一次记录的值和本次相同时，增加计数
count++;
result = nums[i];
} else {
//当上一次记录的值和本次不相同时，减少计数
count--;
}
}
//最后记录的值，一定是众数
return result;
}

private static int MajorityElement3(int[] nums) {
//基于一个事实，排序后的数组最中间的那个数一定是众数
Array.Sort(nums);
return nums[nums.Length / 2];
}

}```

```2
2
2```