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

前提：数组 numbers 存在多数元素，即 count >= [N/2] + 1

本题分治算法思想：
1、将数组一分为二，在左子序列中递归寻找多数元素并记录其出现次数，在右子序列中寻找多数元素并记录其出现次数。
2、遍历当前序列，在左子序列中继续计算右子序列的多数元素的出现次数，在右子序列中继续计算左子序列的多数元素的出现次数。
3、得到左右子序列的多数元素及其在当前序列中的出现次数，选择出现次数多的多数元素进行返回。
4、递归出口是当前序列只有一个元素，返回当前元素，及其出现次数1。

命题1：若数组 numbers 存在多数元素 mostElem，则将数组一分为二为左右子序列后，mostElem 必是左右子序列中的一个序列的多数元素。

证：（反证）设 mostElem 是数组 numbers 的多数元素，将数组一分为二后，mostElem 既不是左子序列的多数元素，也不是右子序列的多数元素.
记左子序列的长度为 L，右子序列的长度为 R，则 L + R = N.
记 mostElem 在左子序列中出现次数为 count1，在右子序列出现次数为 count2.
则 count1 <= [L/2]， count2 <= [R/2]
则 count1 + count2 <= [L/2] + [R/2] < [(L + R) / 2] + 1 = [N/2] + 1
则 mostElem 不是数组 numbers 的多数元素，与命题条件矛盾.
所以原命题成立，即 mostElem 必是左右子序列中的一个序列的多数元素.

在命题1的基础上，证明上述算法的正确性：
命题2：无论递归深度多深，分治算法总能找到正确的多数元素。

证：（归纳）当递归深度为1时，当前序列为原数组 numbers，根据命题1，可知 numbers 的多数元素 mostElem 必定是左右子序列中的一个序列的多数元素.
当递归返回左右子序列的多数元素（记为 mostElem 和 otherElem）及其出现次数后，再次遍历 numbers，得出左右子序列的多数元素的出现次数，此时必定是原多数元素 mostElem 的出现次数更多，因此返回 mostElem.

假设当递归深度为 n 时，当前序列为 numbers 的一个子序列 A，其多数元素为 mostElem，根据命题1，其左右子序列必有一个序列的多数元素为 mostElem.
假设左子序列 A1 的多数元素为 mostElem，右子序列 A2 的多数元素不是 mostElem，记为 otherElem1.
当递归深度为 n + 1 时，A1 分为左子序列 A11 和 右子序列 A12，A2 分为左子序列 A21 和 右子序列 A22，根据命题1，A1 的左右子序列中必有一个序列的多数元素为 mostElem，假设 A11 的多数元素不是 mostElem，记为 otherElem2，A12 的多数元素时 mostElem.

当递归回溯的时候，A11、A12 的多数元素分别为 otherElem2、mostElem，并且计算出 otherElem2 在 A11 的出现次数为 l_count11，mostElem 在 A12 出现次数为 r_count12，此时将遍历 A1 序列，统计 otherElem2 与 mostElem 在序列 A1 的出现次数分别为 s_count11 和 s_count12，因为 mostElem 是 A1 的多数元素，其出现次数 s_count12 >= [len(A1)/2] + 1，因此 otherElem2 的出现次数 s_count11 < [len(A1)/2] + 1，因此 mostElem 将被作为多数元素返回，返回结果与实际结果相同.
递归回溯一层后，A1 返回的多数元素为 mostElem，同理， A2 返回的多数元素为 otherElem1，并同时返回了其出现次数 l_count1、r_count2，遍历 A 序列，统计 mostElem 与 otherElem1 在序列 A 的出现次数分别为 s_count1 和 s_count2，因为 mostElem 是 A 的多数元素，其出现次数 s_count1 >= [len(A)/2] + 1，因此 otherElem1 的出现次数 s_count2 < [len(A)/2] + 1，因此 mostElem 将被作为多数元素返回，返回结果与实际结果相同.

因此，该分治算法总能找到正确的多数元素.

此外讨论两种较为特殊的情况：
命题3：当子序列的多数元素不是 mostElem 时，总能在回溯过程中最终找到正确的多数元素。
证：根据命题2可知，随着递归深度的增加，总会有一个子序列保持原序列的正确的多数元素，在递归回溯时，该分支总会返回正确的结果.
当子序列的多数元素不是 mostElem 时，随着二分法构成的二叉树的向上合并，总会与正确的分支进行合并，此时需要遍历父序列，而正确的多数元素将会胜出。其过程类似于证明命题2中的 A2 返回的是 otherElem1，但会在遍历 A 时，otherElem1 与 mostElem 选出正确的结果返回.

命题4：当左右子序列的多数元素不同且出现次数相等时，总能在回溯过程中最终找到正确的多数元素。
证：无论左右子序列的多数元素是否是 mostElem，该序列都没有多数元素。记左子序列（长度为 L）的多数元素为 elem1, 右子序列（长度为 R）的多数元素为 elem2，出现次数均是 count1，则 count1 >= [L/2] + 1 且 count1 >= [R/2] + 1.
假设存在其他元素有可能是多数元素。考虑极端情况，该序列除了 elem1 和 elem2，其余元素均是 elem3，考虑 elem3 有无可能是当前序列的多数元素.
elem3 的出现次数 count2 = L + R - 2 * count1 <= L + R - [L/2] - [R/2] - 2.
因为 [L/2] + [R/2] + 2 >= [(L + R) / 2] + 1
所以 L + R - ([L/2] + [R/2] + 2) < [(L + R) / 2] + 1
因此 elem3 不可能成为当前序列的多数元素.

代码：

class Solution {
public:
    vector<int> SearchMostInSublist(const vector<int>& elements, int left, int right) {
        // 递归出口，只有一个元素
        if (left == right) {
            return vector<int>{elements[left], 1};  // 第一位表示多数元素，第二位表示出现次数
        }

        // 二分法查找左右子序列的多数元素
        int mid = (left + right) / 2;
        vector<int> leftMost = SearchMostInSublist(elements, left, mid);
        vector<int> rightMost = SearchMostInSublist(elements, mid + 1, right);

        if (leftMost[0] == rightMost[0]) {
            return vector<int>{leftMost[0], leftMost[1] + rightMost[1]};
        }

        // 在左子序列计算右众数出现次数
        for (int i = left; i <= mid; i++) {
            if (elements[i] == rightMost[0]) {
                rightMost[1]++;
            }
        }
        // 在右子序列计算左众数出现次数
        for (int i = mid + 1; i <= right; i++) {
            if (elements[i] == leftMost[0]) {
                leftMost[1]++;
            }
        }
        return leftMost[1] > rightMost[1] ? leftMost : rightMost;
    }

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        return SearchMostInSublist(numbers, 0, numbers.size() - 1)[0];
    }
};

参考题解：
https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/