题解 | # 数组中出现次数超过一半的数字#

JZ28 数组中出现次数超过一半的数字

题意分析

找出数组中出现次数大于数组长度一半的数字。

示例输入：input = [1,2,3,2,2,2,5,4,2]
返回：2
解释：在input数组中，数组的长度为9,数字2出现的次数为5，大于 $\frac{9}{2}$ 。因此返回值为2；

题解一（数字统计）：

我们对给定的数组进行数字统计，对于示例输入，统计结果如下：

数字	1	2	3	4	5
个数	1	5	1	1	1

数据结构使用哈希表即可。对数字和其出现的次数建立一个k-v键对。使用stl的map进行统计。

int MoreThanHalfNum_Solution(vector<int> numbers) {
    map<int, int> table;
    for (auto num:numbers) {
        table[num]++;
    }
    for (auto i:table) {
        if (i.second > numbers.size() / 2) {
            return i.first;
        }
    }
    return 0;
}

时间复杂度：遍历input数组，并且插入到map中，map的插入时间复杂度为 $O(log n)$ ，因此非确切上界时间复杂度为 $O(nlog\ n)$ ， $n$ 为input数组长度。

空间复杂度： $O(n)$ ，n为input数组长度。

题解二（排序）：

题目要求我们找出现次数大于数组长度一半的数字。这个一半有啥字用呢？题解一可以找到任意要求的数字。对于这个一半，想到如果将input数组排序后，会变成怎样？对于示例input数组排序后结果为 $[1,2,2,2,2,2,3,4,5]$ 。我们可以观察到，大于数组长度一半的元素一定分布在数组的中间。

int MoreThanHalfNum_Solution(vector<int> numbers) {
    sort(numbers.begin(), numbers.end());
    return numbers[numbers.size()/2];
}

时间复杂度：排序时间复杂度为 $O(nlog \ n)$ ，n为input数组长度。总的时间复杂度为 $O(nlog\ n)$ 。

空间复杂度： $O(1)$ 。普通的排序不需要额外的空间。

题解三（分治法）：

我们怎么才能将分治法运用到该问题上呢？

考虑将输入数组input平均分成两部分part A，这部分长度为 $l,$ 和part B，这部分长度为 $r$ 。那么对于这两部分会有如下规律：

part a部分存在一个众数 $a$ ,part b部分存在一个众数 $b$ 。很明显a和b其中必定有一个是全局数组的众数。
我们使用反证法证明：如果 $a$ 和 $b$ 都不是全局数组的众数。那么一定存在不同于 $a$ 和 $b$ 的数 $c$ 作为全局数组的众数。

数 $a$ 的个数 $\geq \frac{1}{2}$ ，数 $b$ 的个数 $\geq \frac{r}{2}$ ，数 $c$ 的个数 $\geq \frac{l+r}{2}$ 。这三个数的总的个数大于 $l+r$ 。这明显是不正确的。因此 $a$ 和 $b$ 其中必定有一个是全局数组的众数。

这样我们将数组分成两边部分，分别求出两部分众数以后，然后合并检查是否为全局的众数即可。

我们使用分治法不断的分治，合并解。在本题中，我们不断的划分数组，直到这部分长度变成了1，长度为1的数组众数显然可得。之后再向上合并求解。过程图如下。

图片说明

值得注意的是，上图在求解左半部分众数时，并不会返回2。左半部分是没有众数的。返回了一个1。不会影响最后结果。

算法

int count_in_range(vector<int> &numbers, int l, int r, int target) {
    int count = 0;
    for (int i = l; i <= r; ++i)
        if (numbers[i] == target)
            ++count;
    return count;
}

int majority_element(vector<int> &numbers, int l, int r) {
    if (l == r) {
        return numbers[l];
    }
    int mid = (l + r) / 2;
    int majority_of_left = majority_element(numbers, l, mid);
    int majority_of_right = majority_element(numbers, mid + 1, r);
    if (count_in_range(numbers, l, r, majority_of_left) > (r - l + 1) / 2)
        return majority_of_left;
    if (count_in_range(numbers, l, r, majority_of_right) > (r - l + 1) / 2)
        return majority_of_right;
    return -1;
}

int MoreThanHalfNum_Solution(vector<int> &numbers) {
    return majority_element(numbers, 0, numbers.size() - 1);
}

时间复杂度： $O(nlog\ n)$ 。分治算法不断的将数组划分成两个部分，之后遍历了一遍。其分治算法时间表达式可以写为 $T(n) = 2T(\frac{n}{2})+n$ 。根据主定理，该递归方程结果为 $T(n)=nlog\ n$ 。

空间复杂度： $O(log\ n)$ 。根据图我们知道，递归的深度和均分后的层数有关。深度为 $log\ n$ .因此空间复杂度为 $O(log\ n)$

题解四（Boyer-Moore 投票算法）：

想象一下，如果把这些数字当做人种，一个数字和另外一个数字打了起来，同归于尽。最后剩下的是不是人数最多的那种人。这里要满足一个条件：某类人的数目一定要大于总人数的一半。

算法步骤：我们选择输入数组中第一个元素作为候选元素candidate，并设置其出现次数为count=1。随后遍历数组。当遇到与candidate相同的元素，count+1;不同的元素，count-1。当count为0的时候，选择下一个元素为候选元素，并且置count=1。遍历到数组的最后，剩下的candidate就是要求的结果。

int MoreThanHalfNum_Solution(vector<int> &numbers) {
    int candidate = numbers[0];
    int count = 1;
    for (int i = 1; i < numbers.size(); i++) {
        if (numbers[i] == candidate) {
            count++;
        } else {
            count--;
        }
        if (count == 0) {
            candidate = numbers[i + 1];
            count++;
        }
    }
    return candidate;
}

时间复杂度： $O(n)$ 。Boyer-Moore 算法只对数组进行了一次遍历。

空间复杂度： $O(1)$ 。Boyer-Moore 算法只需要常数级别的额外空间。