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

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

示例 1：

输入：[3,2,3]
输出：3
示例 2：

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

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

1 class Solution {
2     public int majorityElement(int[] nums) {
3         // 排序
4         Arrays.sort(nums);
5         return nums[nums.length/2];
6     }
7 }

 1 class Solution {
 2     public int majorityElement(int[] nums) {
 3         // 投票算法
 4         // 记录选中一个数当众数后，获取的支持数
 5         int count = 0;
 6         // 选中候选者
 7         int candidate = 0;
 8         for(int num:nums){
 9             if (count == 0){
10                 candidate = num;
11             }
12             count += (candidate == num)?1:-1;
13         }
14         return  candidate;
15     }
16 }

 

解题关键：

1.对于排序算法，中间数肯定是众数

2.对于投票算法，极端情况，只有众数和A，A的支持票肯定小于众数的支持票