Difficulty: Easy

Solution 1:

很容易想到的计数法

class Solution {
  public:
    int majorityElement(vector < int > & nums) {
      unordered_map < int, int > m;
      for (int i: nums) {
        if (m.count(i) == 1)
          m[i]++;
        else
          m[i] = 0;
      }
      for (auto & kv: m) {
        if (kv.second >= nums.size() / 2)
          return kv.first;
      }
      return 0;
    }
};

Solution 2:

题目中进一步要求，空间复杂度 O(1)，所以改用先排序，再取中位数

class Solution {
  public:
    int majorityElement(vector < int > & nums) {
      sort(nums.begin(), nums.end());
      return nums[nums.size() / 2];
    }
};

Solution 3:

前法中的时间复杂度为O(nlogn)，还有优化的空间。此方法叫做Boyer-Moore投票法，时间复杂度为O(n),空间复杂度为O(1)。

class Solution {
  public:
    int majorityElement(vector < int > & nums) {
      int maj;
      int count = 0;
      for (int num: nums) {
        if (count == 0) maj = num;
        if (num == maj) {
          count++;
        } else {
          count--;
        }
      }
      return maj;
    }
};