169.求众数

发表于 更新于 分类于 ，

题目

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

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

示例 1:

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

示例 2:

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

思路

这道题由于题目已经明确了众数是出现次数大于n/2次,所以就可以得到一个规律:只要将这个数组进行排序,那数组中间的那个数无论如何都会是众数,因为众数占据了长度的一半以上.

所以这道题可以有两种解法:

  • 直接返回排序之后数组的一半位置的数.
  • 用一个哈希表记录数字出现的次数,如果多于一半就是众数

代码

排序法

1
2
3
4
5
public int MajorityElement(int[] nums)
{
    Array.Sort(nums);
    return nums[nums.Length / 2];
}

哈希表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int MajorityElement(int[] nums)
{
    Dictionary<int, int> numsInfo = new Dictionary<int, int>();
    foreach (var num in nums)
    {
        if (numsInfo.ContainsKey(num))
        {
            numsInfo[num]++;
        }
        else
        {
            numsInfo.Add(num, 1);
        }
        if (numsInfo[num] > nums.Length / 2)
        {
            return num;
        }
    }
    return 0;
}