229.Majority-Element-II

229. Majority Element II

题目地址

https://leetcode.com/problems/majority-element-ii/

题目描述

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:
Input: [3,2,3]
Output: [3]

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

代码

Approach #1 Boyer Moore

class Solution {
  public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
    if (nums == null || nums.length == 0)        return ans;
    int count1 = 0, count2 = 0;
    int candidate1 = 0, candidate2 = 1;
    for (int num: nums) {
      if (num == candidate1)    count1++;
      else if (num == candidate2)  count2++;
      else if (count1 == 0) {
        candidate1 = num;
        count1 = 1;
      }
      else if (count2 == 0) {
        candidate2 = num;
        count2 = 1;
      }
      else {
        count1--;
        count2--;
      }
    }

    count1 = 0;
    count2 = 0;
    for (int num: nums) {
      if (num == candidate1)    count1 += 2;
      else count1--;
      if (num == candidate2)    count2 += 2;
      else count2--;
    }

    if (count1 > 0)        ans.add(candidate1);
    if (count2 > 0)        ans.add(candidate2);
    return ans;
  }
}