给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

暴力算法

可以先统计出各个元素出现的次数，然后找到那个次数大于 n/2 的元素：

  1. public int majorityElement(int[] nums) {
  2.     Map<Integer, Integer> countMap = countNum(nums);
  4.     int limit = nums.length/2;
  5.     for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
  6.         if (entry.getValue() > limit) {
  7.             return entry.getKey();
  8.         }
  9.     }
  11.     return -1;
  12. }
  14. private Map<Integer, Integer> countNum(int[] nums) {
  15.     Map<Integer, Integer> counts = new HashMap<>();
  16.     for (int num : nums) {
  17.         if (!counts.containsKey(num)) {
  18.             counts.put(num, 1);
  19.         } else {
  20.             counts.put(num, counts.get(num) + 1);
  21.         }
  22.     }
  23.     return counts;
  24. }

技巧算法

假设偶数元素数量数组：[2,2,1,1,1,2,2]，对数组进行升序排序：[1,1,1,2,2,2,2]
假设奇数元素数量数组：[1,1,2,2,1,2,2,2]，对数组进行升序排序：[1,1,1,2,2,2,2]
可以发现，数组 n/2 位置的元素必定是多数元素：

  1. public int majorityElement(int[] nums) {
  2.     Arrays.sort(nums);
  3.     return nums[nums.length / 2];
  4. }

摩尔投票

候选人(cand_num) 初始化为 nums[0]，票数 count 初始化为 1。
当遇到与 cand_num 相同的数，则票数 count = count + 1，否则票数 count = count - 1。
当票数 count 为0时，更换候选人，并将票数 count 重置为1。
遍历完数组后，cand_num 即为最终答案。

原理是：
投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。

  1. public int majorityElement(int[] nums) {
  2.     int cand_num = nums[0], count = 1;
  3.     for (int i = 1; i < nums.length; ++i) {
  4.         if (cand_num == nums[i]) {
  5.             ++count;
  6.         } else if (--count == 0) {
  7.             cand_num = nums[i];
  8.             count = 1;
  9.         }
  10.     }
  11.     return cand_num;
  12. }