寻找数组中出现次数超过一半的元素

一个数组中，有某个元素的出现次数超过数组中元素个数的一半，找出这个元素。

这题有一些较容易想到的常规做法：

1. 先排序，中间元素即为所需元素。时间复杂度O(lonN)。
2. 利用散列，统计每个元素出现的次数，超过一半即输出。此算法需要额外空间，约为O(n)。

不过这两种方法都未能在时间和空间上同时达到最优，在牛客网上做到这题时，评论区中有个给出了一个来源于《编程之美》中的巧妙算法，可以做到只循环一遍，且不需要额外空间。

算法基本思路是：在数组中任选两个不同元素消去，最终剩下的元素一定是出现次数超过一半的元素（在保证此元素存在的情况下）。

具体编程时，可以重头开始扫描，记录当前元素出现次数times，遇到不同的元素则times--，若times==0，换一个元素继续。代码如下：

int getMode(int Nums[], int n) {
    int remain, times = 0;
    
    for (int i = 0; i < n; i++) {
        if (times == 0) {
            remain = Nums[i];
        }
        if (remain == Nums[i]) {
            times++;
        } else {
            times--;
        }
    }
    
    return remain;
}

此算法需要预先保证输入元素中肯定存在解时返回结果才正确，若不确定是否有元素出现次数大于一半，需要在最后再循环检查一遍：

times = 0;
for (int i = 0; i < n; i++){
    if (Nums[i] == remain)
        times++;
}
return (times > n / 2 ? remain : -1);