题目

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

  1. Input: [3,2,3]
  2. Output: [3]

Example 2:

  1. Input: [1,1,1,3,3,2,2,2]
  2. Output: [1,2]

题意

找到数组中所有出现次数大于⌊ n/3 ⌋的元素。

思路

限制时间为O(N)、空间为O(1)，因此不能用Hash或者排序。使用 0169. Majority Element (E) 中提到的摩尔投票法 Boyer-Moore Majority Vote。求所有出现次数大于⌊ n/3 ⌋的元素，用反证法很容易证明这种元素最多只有两个，所以可以先用摩尔投票法获得两个候选元素，再重新遍历数组统计候选元素出现的次数，将满足条件的加入到结果集中。

代码实现

Java

  1. class Solution {
  2.     public List<Integer> majorityElement(int[] nums) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         int a = 0, b = 0;
  5.         int countA = 0, countB = 0;
  6.         for (int i = 0; i < nums.length; i++) {
  7.             if (nums[i] == a) {
  8.                 countA++;
  9.             } else if (nums[i] == b) {
  10.                 countB++;
  11.             } else if (countA == 0) {
  12.                 a = nums[i];
  13.                 countA = 1;
  14.             } else if (countB == 0) {
  15.                 b = nums[i];
  16.                 countB = 1;
  17.             } else {
  18.                 countA--;
  19.                 countB--;
  20.             }
  21.         }
  22.         countA = 0;
  23.         countB = 0;
  24.         for (int i = 0; i < nums.length; i++) {
  25.             if (nums[i] == a) {
  26.                 countA++;
  27.             } else if (nums[i] == b) {
  28.                 countB++;
  29.             }
  30.         }
  31.         if (countA > nums.length / 3) {
  32.             ans.add(a);
  33.         }
  34.         if (countB > nums.length / 3) {
  35.             ans.add(b);
  36.         }
  37.         return ans;
  38.     }
  39. }

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var majorityElement = function (nums) {
  6.   let ans = []
  7.   let a = 0, b = 0, countA = 0, countB = 0
  9.   for (let num of nums) {
  10.     if (num === a) {
  11.       countA++
  12.     } else if (num === b) {
  13.       countB++
  14.     } else if (countA === 0) {
  15.       a = num
  16.       countA = 1
  17.     } else if (countB === 0) {
  18.       b = num
  19.       countB = 1
  20.     } else {
  21.       countA--
  22.       countB--
  23.     }
  24.   }
  26.   countA = 0, countB = 0
  27.   for (let num of nums) {
  28.     if (num === a) {
  29.       countA++
  30.     } else if (num === b) {
  31.       countB++
  32.     }
  33.   }
  35.   if (countA > Math.trunc(nums.length / 3)) ans.push(a)
  36.   if (countB > Math.trunc(nums.length / 3)) ans.push(b)
  38.   return ans
  39. }