LeetCode 169. 求众数

题目描述

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

题解

排序法

算法

设有排序后的数组如下图：

其中蓝色为元素坐标 n/2 ，红线为众数出现的位置，无论数组个数为奇数或偶数， 坐标 n/2 处肯定为众数。

代码

// C++
int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size()/2];
}

复杂度分析

• 时间复杂度： $O(n\log{n})$ ，排序需要 $O(n\log{n})$ 。
• 空间复杂度： $O(1)$ 。

哈希表

思路

使用哈希表来记录数出现的次数，判断是否大于 n/2 。

代码

// C++
int majorityElement(vector<int>& nums) {
    unordered_map<int, int> map;
    for (auto n : nums) {
        map[n]++;
    }
    for (auto p : map) {
        if (p.second > nums.size()/2) {
            return p.first;
        }
    }
    return -1;
}

复杂度分析

• 时间复杂度： $O(n)$ ，需要遍历数组和哈希表。
• 空间复杂度： $O(n)$ ，哈希表需要存储至多 $n-\lfloor{\frac{n}{2}\rfloor}$ 个元素。

Boyer–Moore majority vote algorithm

算法

很巧妙的算法，Wikipedia 定义 。算法如下：

• 定义众数候选 cadidate 和计数器 count 。
• 遍历数组：如果 count == 0 ，则将当前元素设为新的候选 cadidate 。
• 如果当前元素 nums[i] == cadidate ，则将 count++，否则 count-— 。

算法理解：

• 算法目标是，找出 nums 的一个后缀数组 nums[i] ~ nums[n-1]，其中 nums[i] 为众数，而前缀数组 nums[0] ~ nums[i-1] 中没有众数。

• 当 i-1 时 count == 0 ，表示之前的候选数的个数已经被非候选数的个数所抵消，此时前缀数组 nums[0] ~ nums[i-1] 中没有众数，需要在后缀数组 nums[i] ~ nums[n-1] 中寻找。

• 在后缀数组中设 nums[i] 为候选，count 为 1 。继续遍历，因为 nums[i] 为众数，后面非众数的个数无法抵消 nums[i] 的个数。

例：

假设有数组：

[7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7]

• 设候选cadidate 为 7 ，此时 count 为 1 。

[7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7]

• 当到 nums[5] = 1 时，count 变为 0 。说明 7 出现的个数已经被抵消完。

[7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7]

• 更换候选为 5 ，则在下一个 7 处被抵消。

[7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7]

• 同理，这个位置也被抵消。

[7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7]

• 最后后缀数组中 nums[12] ~ nums[15] 中，可以确定 7 为众数。

代码

// C++
int majorityElement(vector<int>& nums) {
    int cadidate = 0;
    int count = 0;
    for (auto n : nums) {
        if (count == 0) {
            cadidate = n;
        }
        count += (cadidate == n) ? 1 : -1;
    }
    return cadidate;
}

复杂度分析

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

分治算法

算法

将问题分为寻找左右半部分数组的众数。

代码

//C++
int majorityElementDivide(vector<int>& nums, int l, int r) {
    if (l == r) {
        return nums[l];
    }
    int m = l + (r - l)/2;
    int leftEle = majorityElementDivide(nums, l, m);
    int rightEle = majorityElementDivide(nums, m + 1, r);
    if (leftEle == rightEle) {
        return leftEle;
    }
    int leftCount = countElementDivide(nums, leftEle, l, r);
    int rightCount = countElementDivide(nums, rightEle, l, r);
    return leftCount > rightCount ? leftEle : rightEle;
}
int countElementDivide(vector<int>& nums, int num, int l, int r) {
    int count = 0;
    for (int i = l; i <= r; ++i) {
        if (nums[i] == num) {
            count ++;
        }
    }
    return count;
}
int majorityElement(vector<int>& nums) {
    if (nums.empty()) {
        return -1;
    }
    return majorityElementDivide(nums, 0, (int)nums.size()-1);
}

复杂度分析

• 时间复杂度： $O(n\log{n})​$ 。
• 空间复杂度： $O(\log{n})$ 。

参考链接

• 169. Majority Element, LeetCode solution.
• Boyer-Moore majority vote algorithm, from Wikipedia.