229. Majority Element II.md

229. Majority Element II

---

leetcode Daily Challenge on September 22th, 2020.

---

Difficulty : Medium

Related Topics : Array

---

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]

---

Solution

same as 169. Majority Element.

• mine
  • Java
    • ``

---

• the most votes

• Boyer-Moore Majority Vote Runtime: 1 ms, faster than 100.00%, Memory Usage: 43.5 MB, less than 56.72% of Java online submissions

  public List<Integer> majorityElement(int[] nums) {
      if (nums == null || nums.length == 0)
          return new ArrayList<>();
      List<Integer> result = new ArrayList<>();
      int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
      for (int i = 0; i < len; i++) {
          if (nums[i] == number1)
              count1++;
          else if (nums[i] == number2)
              count2++;
          else if (count1 == 0) {
              number1 = nums[i];
              count1 = 1;
          } else if (count2 == 0) {
              number2 = nums[i];
              count2 = 1;
          } else {
              count1--;
              count2--;
          }
      }
      count1 = 0;
      count2 = 0;
      for (int i = 0; i < len; i++) {
          if (nums[i] == number1)
              count1++;
          else if (nums[i] == number2)
              count2++;
      }
      if (count1 > len / 3)
          result.add(number1);
      if (count2 > len / 3)
          result.add(number2);
      return result;
  }
  

---