C#LeetCode刷题之#169-求众数(Majority Element)

C#LeetCode刷题之#169-求众数(Majority Element)

问题

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

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

输入: [3,2,3]

输出: 3

输入: [2,2,1,1,1,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:

示例

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的时间复杂度均为: O(n)​ ,MajorityElement3的时间复杂度基于Array.Sort()所使用的排序算法。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4048

发表评论

登录后才能评论