1 题目

169-多数元素

2 思路

首先想到哈希表，key是元素值，value是元素的个数，取个数最大的key。虽然时间复杂度为 O(n)，但空间复杂度为 O(n)，不符合题意的 O(1)；

然后想到排序，排序后取中间元素。可是排序（如快排）的时间复杂度为 O(nlogn)，不符合题意的 O(n)；

又想到其实不用全部排序好，只要找到中间的元素就可以，但是好像没有好的办法，快排的第一遍排完序，有序的那个元素也不是恰好是中间元素；没有好办法了，直接看官方题解吧。

3 题解

3.1 哈希表

对每个元素进行计数，取数量最大的元素。时间复杂度：O(n)，空间复杂度：O(n)。

class Solution {
 public:
  int majorityElement(vector<int>& nums) {
    unordered_map<int, int> nums_map;
    int res = 0, res_count = 0;

    for (int num : nums) {
      ++nums_map[num];
      if (nums_map[num] > res_count) {
        res = num;
        res_count = nums_map[num];
      }
    }
    return res;
  }
};

3.2 排序

使用sort()排序，取中间位置的元素。由于题目中说众数的数量大于一半，所以中间位置的元素一定是众数。时间复杂度：O(nlogn)，空间复杂度：O(logn)。

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

3.3 随机化

虽然这个方法乍看起来很扯，但是研究起来很有意思。

由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它是否是众数，如果是就返回，否则继续随机挑选。时间复杂度：O(∞)，空间复杂度：O(1)。

计算随机的期望次数（下标为 prob 为原问题，mod 为众数恰好占据数组一半数目的问题）：E(iters_prob​)​ ≤ E(iters_mod​) = lim​_n→∞∑_i=1^n​ (i⋅1/2ⁱ) = 2。

class Solution {
 public:
  int majorityElement(vector<int>& nums) {
    while (true) {
      int candidate = nums[rand() % nums.size()];
      int count = 0;

      for (int num : nums) {
        if (candidate == num) ++count;
      }

      if (count > nums.size() / 2) return candidate;
    }
  }
};

3.4 分治

时间复杂度：O(nlogn)，空间复杂度：O(logn)。

class Solution {
  int count_in_range(vector<int>& nums, int target, int lo, int hi) {
    int count = 0;
    for (int i = lo; i <= hi; ++i) {
      if (nums[i] == target) ++count;
    }
    return count;
  }

  int majority_element_rec(vector<int>& nums, int lo, int hi) {
    if (lo == hi) return nums[lo];

    int mid = (lo + hi) / 2;
    int left_majority = majority_element_rec(nums, lo, mid);
    int right_majority = majority_element_rec(nums, mid + 1, hi);
    if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
      return left_majority;
    if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
      return right_majority;
    // 当左和右都不是众数时，可以返回任意值，不影响最终结果
    return -1;
  }

 public:
  int majorityElement(vector<int>& nums) {
    return majority_element_rec(nums, 0, nums.size() - 1);
  }
};

3.5 Boyer-Moore 投票算法 (最佳题解)

一言以蔽之，如果一个众数对应一个非众数，两个数一起消掉，最终剩下的一定是众数。

时间复杂度：O(n)，空间复杂度：O(1)。

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

    for (int num : nums) {
      if (count == 0) {
        candidate = num;
        count = 1;
        continue;
      }

      if (candidate != num) {
        --count;
        continue;
      }

      ++count;
    }

    return candidate;
  }
};