LeetCode 169: Majority Element

Difficulty: Easy

Tags: Array, Divide and Conquer, Bit Manipulation

问题描述

有一个非空的大小为n的数组，其中有一个元素出现了超过[n/2]次，找出这个元素。

解决方案

关于这个问题，需要想通一点：

在一个有Majority Element的数组中，移除2个不同的元素，在剩余的数组中Majority Element依然维持不变。

再细节一点，分成2种情况考虑：

▷ Majority Element在移除的2个不同元素中，那移除的2个元素一个是Majority Element一个不是，Majority Element在剩余的数组还是超过半数。

▷ Majority Element不在移除的2个不同元素中，显然Majority Element在剩余的数组中仍然超过半数。

Majority Element的定义还可以引申一下，引申为在数组中出现超过[n/k]次。那么数组移除k个不同的元素，在剩余的数组中Majority Element依然维持不变。

在本题中，k等于2。

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
  int majorityElement(vector<int> &nums) {
    int major;
    int count = 0;

    for (int i = 0; i < nums.size(); i++) {
      if (count == 0) {
        major = nums[i];
        count = 1;
      } else {
        if (major == nums[i])
          count++;
        else
          count--;
      }
    }
    return major;
  }
};

回到 Conquer Leetcode