本题的难点在于理解多数投票算法(Boyer-Moore Voting Algorithm)，
先上代码:

  1. class Solution {
  2.     public List<Integer> majorityElement(int[] nums) {
  3.         List<Integer> result = new ArrayList<>();
  4.         if (nums == null || nums.length == 0) {
  5.             return result;
  6.         }
  7.         int num1 = nums[0];
  8.         int num2 = nums[0];
  9.         int count1 = 0;
  10.         int count2 = 0;
  11.         for (int i = 0; i < nums.length; ++i) {
  12.             if (nums[i] == num1) {
  13.                 ++count1;
  14.             }
  15.             else if (nums[i] == num2) {
  16.                 ++count2;
  17.             }
  18.             else if (count1 == 0) {
  19.                 num1 = nums[i];
  20.                 count1 = 1;
  21.             }
  22.             else if (count2 == 0) {
  23.                 num2 = nums[i];
  24.                 count2 = 1;
  25.             }
  26.             else {
  27.                 --count1;
  28.                 --count2;
  29.             }
  30.         }
  31.         count1 = 0;
  32.         count2 = 0;
  33.         for (int i = 0; i < nums.length; ++i) {
  34.             if (nums[i] == num1) {
  35.                 ++count1;
  36.             }
  37.             else if (nums[i] == num2) {
  38.                 ++count2;
  39.             }
  40.         }
  41.         if (count1 > nums.length / 3) {
  42.             result.add(num1);
  43.         }
  44.         if (count2 > nums.length / 3) {
  45.             result.add(num2);
  46.         }
  47.         return result;
  48.     }
  49. }

这是关键部分：

  1. if (nums[i] == num1) {
  2.     ++count1;
  3. }
  4. else if (nums[i] == num2) {
  5.     ++count2;
  6. }
  7. else if (count1 == 0) {
  8.     num1 = nums[i];
  9.     count1 = 1;
  10. }
  11. else if (count2 == 0) {
  12.     num2 = nums[i];
  13.     count2 = 1;
  14. }
  15. else {
  16.     --count1;
  17.     --count2;
  18. }
  • 如果一个num1的数量大于n/3，则需要至少同等数量的Fail Call(else path)才能抹除它，此时，意味着已经调用过n/3次--count2，所以关于num2的增操作(以及赋值操作)也至少有n/3。这就证明一旦有n/3个，就一定会被保留下来

  • 只要弄明白--操作不可能多于n/3，本题就不难

  • 时间复杂度：229. Majority Element II - 图1

  • 空间复杂度：229. Majority Element II - 图2

Update July/13/2020

  • 重新做又没有做出来