Skip to content

229. Majority Element II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    vector<int> ans;
    int candidate1 = 0;
    int candidate2 = 1;   // any number different from candidate1
    int countSoFar1 = 0;  // the number of candidate1 so far
    int countSoFar2 = 0;  // the number of candidate2 so far

    for (const int num : nums)
      if (num == candidate1) {
        ++countSoFar1;
      } else if (num == candidate2) {
        ++countSoFar2;
      } else if (countSoFar1 == 0) {  // Assign the new candidate.
        candidate1 = num;
        ++countSoFar1;
      } else if (countSoFar2 == 0) {  // Assign the new candidate.
        candidate2 = num;
        ++countSoFar2;
      } else {  // Meet a new number, so pair with the previous counts.
        --countSoFar1;
        --countSoFar2;
      }

    const int count1 = ranges::count(nums, candidate1);
    const int count2 = ranges::count(nums, candidate2);

    if (count1 > nums.size() / 3)
      ans.push_back(candidate1);
    if (count2 > nums.size() / 3)
      ans.push_back(candidate2);
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  public List<Integer> majorityElement(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    int candidate1 = 0;
    int candidate2 = 1;  // any number different from candidate1
    int countSoFar1 = 0; // the number of candidate1 so far
    int countSoFar2 = 0; // the number of candidate2 so far

    for (final int num : nums)
      if (num == candidate1) {
        ++countSoFar1;
      } else if (num == candidate2) {
        ++countSoFar2;
      } else if (countSoFar1 == 0) { // Assign the new candidate.
        candidate1 = num;
        ++countSoFar1;
      } else if (countSoFar2 == 0) { // Assign the new candidate.
        candidate2 = num;
        ++countSoFar2;
      } else { // Meet a new number, so pair with the previous counts.
        --countSoFar1;
        --countSoFar2;
      }

    int count1 = 0;
    int count2 = 0;

    for (final int num : nums)
      if (num == candidate1)
        ++count1;
      else if (num == candidate2)
        ++count2;

    if (count1 > nums.length / 3)
      ans.add(candidate1);
    if (count2 > nums.length / 3)
      ans.add(candidate2);
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def majorityElement(self, nums: List[int]) -> List[int]:
    ans1 = 0
    ans2 = 1
    count1 = 0
    count2 = 0

    for num in nums:
      if num == ans1:
        count1 += 1
      elif num == ans2:
        count2 += 1
      elif count1 == 0:
        ans1 = num
        count1 = 1
      elif count2 == 0:
        ans2 = num
        count2 = 1
      else:
        count1 -= 1
        count2 -= 1

    return [ans for ans in (ans1, ans2) if nums.count(ans) > len(nums) // 3]