寻找多数元素

【问题描述】给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

【输入形式】输入的第1行中有1个数字n，表示数组的长度；第2行中有n个数字，表示数组的元素

【输出形式】输出1行一个数字表示该数组中的多数元素。
【样例输入】

3

1 2 1
【样例输出】

2

【说明】
1 <= n <= 10^5

-10^9 <= nums[i] <= 10^9

题解：

下面介绍的是时间复杂度为O(n)的解法：

在一个长度为n的数组中，出现次数超过n/2的元素称为多数元素，这也就注定了数组中最多只会有一个多数元素。

现在，假设从数组中取出两个不相同的元素，则可能出现的情况有：

• 一个为多数元素，一个为非多数元素
• 两个都是非多数元素

第一种情况：

从数组中取出两个元素，则新数组长度为n-2，多数元素的个数也相应减1；此时，要证明原来的多数元素仍为新数组的多数元素，则需要证明num-1>=(n-2)/2的正确性。在取元素之前，多数元素的个数num便已经满足num>=n/2，所以，很容易证明得到前式的正确性。

第二种情况：

数组整体长度减二，但是多数元素个数却不变，很显然，这种情况下，原来的多数元素仍为新数组的多数元素。

因此，可以得出的结论是：从数组中任意的拿走两个不同的元素，则原来数组中的多数元素仍为新数组的多数元素。（注意此条件的逆命题是不一定成立的）

现在我就基于这个原理，设计一个算法：

int candidate(int k) {
    if (k <= n) {
        int cnt = 1, i = k;
        while(i < n && cnt > 0){
            i++;
            if (a[i] == a[k]) {
                cnt++;
            }
            else {
                cnt--;
            }
        }
        if (i == n)
            return k;
        else
            return candidate(i + 1);
    }
    else
        return -1;
}

函数返回值为新数组多数元素的下标，假设第k个元素是当前数组中多数元素的候选者，设置一个计数器cnt初始化为1，扫描以第k + 1个元素为起始点：

• 如果a[i]==a[k]，则cnt++；
• 如果a[i]!=a[k]，则cnt--；
• 假如数组中存在多数元素：
• 一旦cnt减小到0，说明已经扫描过的元素一定可以组合成成对的不相同元素，假如数组中本来就存在多数元素，去掉他们之后原数组的多数元素仍然是新数组的多数元素（根据上文提到的结论）。此时，退出循环，将第i+1个元素假定为新的多数元素候选者，继续在新数组中搜索。
• 但循环的中止条件不仅有cnt>0，还有ii==n，翻译成文字也就是忽略最后一个元素，循环按部就班的做完了，没有被中途打断。而i==n也可以分为两种情况：1. i==n&&cnt>0；2.  i==n&&cnt==0。
• 这两种情况是有所区别的，虽然都可以确定多数元素在第k个位置：

1. 若 cnt>0 ，那么说明第k个元素就是当前数组的多数元素（注意是当前数组，因为现在搜索的范围可能是在拿掉几对不相同元素之后得到的新数组），最后一个元素不用管了，如果它和第k个元素不相等，那它也一定不是多数元素，那就直接return k就完事了。
2. 若cnt==0，这时，假如原数组多数元素存在，根据之前的去掉成对不同元素之后，原数组的多数元素仍是新数组多数元素的结论，在新数组就剩一个元素的条件下，则那它一定就是新数组的多数元素，并且它肯定和a[k]相等——为什么相等？因为既然cnt正好减到了0，那假如当前数组的长度为n，那a[k]出现的次数必然是(n-1)/2，又因为最后一个元素是多数元素，只有最后一个元素与a[k]相等时，才能使得最后一个元素在当前数组中的出现次数超过n/2。

• 如果数组中本来就不存在多数元素，函数可能会一直递归到k>n，此时返回一个-1，说明不存在。

以上函数的时间复杂度是O(n)，只需要完整的扫描一遍数组即可。

但这个函数返回的不一定就是原数组的多数元素，原因是之前介绍的结论的逆命题并不一定成立，如果数组中本就不存在多数元素，函数的返回值也有可能不是-1，因为有些元素可能在整个数组不是多数元素，但在新数组中却是的，比如：

2，1，4，4

2，1，4，4

这时候，函数肯定会返回第一个4的下标，但这显然，4就不是多数元素。

so，在接受完函数返回值后，还要验证一遍4的数量到底是不是大于n/2。这个时间复杂度也是线性的。

完整代码就是：

#include 
using namespace std;
int n, a[100001];
 
int candidate(int k) {
    if (k <= n) {
        int cnt = 1, i = k;
        while(i < n && cnt > 0){
            i++;
            if (a[i] == a[k]) {
                cnt++;
            }
            else {
                cnt--;
            }
        }
        if (i == n)
            return k;
        else
            return candidate(i + 1);
    }
    else
        return -1;
}
 
 
int main()
{
    cin >> n; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int k = candidate(1), sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[k]) {
            sum++;
        }
    }
    if (sum > n / 2) {
        cout << a[k];
    }
    return 0;
}

新增两种不同的实现方式

1. 分治

class Solution {
    int count(vector<int>& nums, int l, int r, int x) {
        int cnt = 0;
        for (int i = l; i <= r; i++) {
            if (nums[i] == x) {
                ++cnt;
            }
        }
        return cnt;
    }
    int getMode(vector<int>& nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int mid = (l + r) / 2;
        int lf_m = getMode(nums, l, mid);
        int rt_m = getMode(nums, mid + 1, r);
        if (lf_m == rt_m) {
            return lf_m;
        } else if (count(nums, l, r, lf_m) > (r - l + 1) / 2) {
            return lf_m;
        } else {
            return rt_m;
        }
    }
public:
    int majorityElement(vector<int>& nums) {
        // 寻找数量大于 n/2 的元素
        return getMode(nums, 0, nums.size() - 1);
    }
};

2. 迭代

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};