LeetCode-169-多数元素

1、投票算法

为了实现时间复杂度为 O(n)，空间复杂度为 O(1) 的算法，我们无法使用哈希表、分治法、排序等方法，因此我们可以考虑使用投票算法。

在开始时，我们可以假设nums[0]是数组的多数元素即候选者，count用于记录候选者元素出现的次数，初始为0。每当我们读入一个新的元素时将其与候选者进行对比，若相等则count+1，若不相等则count-1。当我们遍历完整个数组时，返回最后的候选者即可。

为了证明上述算法的正确性，我们可以考虑以下几点：当count从1变成0时，我们将先前的区间单独划分出来，在这个区间中的候选元素的个数一定等于剩余元素的个数。1、若此时的候选元素就是整个数组的多数元素，则此时候选元素的个数等于其他元素的个数，在区间右边的部分中，真正的多数元素即候选元素的个数一定多于其他元素的总和；2、若此时的候选元素不是整个数组的多数元素，那么此时在区间中，真正的多数元素个数一定小于等于此时的候选元素，因此区间右侧的真正多数元素的个数一定多于其他元素。因此我们不难看出，不管在什么时候，最后一个区间中的多数元素个数一定多于其他元素的总和，因此count一定大于0，故此时的候选元素就是最终数组的多数元素。

int candidate = -1;
    int count = 0;
    for (int num : nums) {
        if (num == candidate)
            ++count;
        else if (--count < 0) {
            candidate = num;
            count = 1;
        }
    }
    return candidate;

2、哈希表

我们可以使用哈希表统计所有元素出现的次数，最终返回哈希表中出现次数最多的元素。时间复杂度为O(n)，空间复杂度为O(n)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

3、排序

将所有元素进行排序后，由于多数元素出现次数多于一半，因此$\lfloor \frac{n}{2}\rfloor$的值一定就是多数元素的值。

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

4、分治法

由于多数元素出现的次数多于数组元素个数的一半，最终的多数元素一定是先前一个子序列中的多数元素。

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);
    }
};