169. 多数元素
#leetcode#hash#投票法 2025-01-31

Problem: 169. 多数元素

解析

hash表

hash表法，遍历数组，记录每个元素出现的次数，最后返回出现次数大于n/2的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//!  n,n
class Solution {
 public:
  int majorityElement(vector<int> &nums) {
    unordered_map<int, int> hashTable;
    for (int i = 0; i < nums.size(); ++i) {
      if (hashTable.find(nums[i]) != hashTable.end()) {
        ++hashTable[nums[i]];
      } else {
        hashTable.insert({nums[i], 1});
      }
    }
    for (auto e : hashTable) {
      if (e.second > nums.size() / 2) {
        return e.first;
      }
    }

    return 0;
  }
};

排序

排序法，排序后，中间元素一定是出现次数大于n/2的元素。

用反证法证明：如果中间元素不是出现次数大于n/2的元素，那么出现次数大于n/2的元素一定在中间元素的左边或右边，那么左边或右边的元素个数大于n/2，与中间元素不是出现次数大于n/2的元素矛盾。

1
2
3
4
5
6
7
8
//! nlog(n),1
class Solution {
 public:
  int majorityElement(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
  }
};

投票法

遍历数组，记录当前元素和次数，如果次数为0，更新当前元素，次数为1，否则次数加一或减一。最后是多数派的胜利

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//! n,1
class Solution {
 public:
  int majorityElement(vector<int> &nums) {
    int winner = nums[0], cnt = 1;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] != winner) {
        --cnt;
        if (cnt < 0) {
          winner = nums[i];
          cnt = 1;
        }
      } else {
        ++cnt;
      }
    }
    return winner;
  }
};