面试题 17.10. 主要元素

本题不难，如果要求时间复杂度 O(N)，空间复杂度 O(1)，只能用投票算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int majorityElement(vector<int>& nums) {
    int n = -1;
    int count = 0;
    for (auto x : nums) {
      if (count == 0 || x == n) {
        n = x;
        count++;
      } else {
        count--;
      }
    }
    count = 0;
    for (auto x : nums) {
      if (x == n) count++;
    }
    if (count > nums.size() / 2) return n;
    return -1;
  }
};