leetcode169：多数元素

题目链接

leetcode

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

/*
    哈希表，记录每个元素出现的次数

    时间复杂度：O(n)
        其中 n 是数组的长度。
    空间复杂度：O(n)
        哈希表占用的空间为 O(n)。
*/
class Solution_0 {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> num2cnt;
        int num, count = 0;
        for (int x : nums) {
            num2cnt[x]++;
            if (count < num2cnt[x]) {
                num = x;
                count = num2cnt[x];
            }
        }
        
        return num;
    }
};

/*
    摩尔投票法
    
    众数记为 +1，其他数记为 −1。
    众数一定比其他数多，将它们全部加起来，和大于 0。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int target = nums[0]; // 众数
        int count = 1; // 计数器

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

        return target;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {3,2,3},
        {2,2,1,1,1,2,2}
    };

    for (auto& nums : nums_cases) {
        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;
        int result = solution.majorityElement(nums);
        cout << "Output: " << result << endl;
    }

    return 0;
}