给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
public int MajorityElement(int[] nums) { int i = 0;//假设的众数指标 int j = 1;//进度指标 int count = 0;//计数 //计数超过一半前 while(count < (nums.Length - i)/2 && j < nums.Length) { if(nums[j] == nums[i]) { count++; } else { count--; } if(count == -1) { //前面为成对不相等的值,抛弃掉,重新计数 i = j + 1; j = i + 1; count = 0; } else { j++;//进度向前 } } return nums[i]; }
解析请查看主元素问题