
问题
给定一个大小为 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()所使用的排序算法。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4048。