题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

题解

排序

排序后，数组中出现次数超过一半的数字一定在中间位置。

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

时间复杂度：O(nlogn)
空间复杂度：O(logn)，sort() 一般情况认为是快排（实际更复杂），有 O(logn) 的递归深度；也可以自己在原数组上实现堆排，空间复杂度为 O(1)。

哈希

遍历数组，统计数字出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> num_count;
        int res = -1;
        for (int i = 0; i < nums.size(); ++i) {
            ++num_count[nums[i]];
            if (num_count[nums[i]] > nums.size() / 2) {
                res = nums[i];
                break;
            }
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

随机选数

因为在数组中出现次数超过一半，我们可以随机选中数组中的一个数，再判定这个数是不是我们想要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while (true) {
            int candidate = nums[rand() % nums.size()];
            int count = 0;
            for (int num : nums) {
                if (candidate == num)
                    count++;
            }
            if (count > nums.size() / 2)
                return candidate;
        }
        return -1;
    }
};

时间复杂度：O(n)，理论上最坏的情况为 O(∞)，也就是我们永远选不到答案；但是因为在数组中出现的次数超过一半，所以选中的概率是大于二分之一的，期望的时间复杂度为 O(n)。
空间复杂度：O(1)

分治

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
    }
};

时间复杂度：O(nlogn)，类比归并排序的二路分治。
空间复杂度：O(logn)，递归深度为 O(logn)，没有其他额外空间。

Boyer-Moore 投票算法

如果数组中两个元素不相等，我们就同时删除这两个元素，最后剩下的一定是出现次数超过一半的数字。

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

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