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

问题

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

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

输入: [3,2,3]

输出: 3

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

输出: 2 

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: 2 

示例

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}");

        Console.ReadKey();
    }

    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];
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

2
2
2

分析：

显而易见，MajorityElement和MajorityElement2的时间复杂度均为： ​ ，MajorityElement3的时间复杂度基于Array.Sort()所使用的排序算法。