题面描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。

思考题：
假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

样例

输入：[1,2,1,1,3]
输出：1

算法1

（暴力枚举） O(n^2)

两个for扫一遍就行

代码鸽了

算法2

(排序) O(nlogn)

将所有数进行排序，出现次数最多的数一定在最中间

题目说了多于一半，所以不存在n/2 - 1的情况

C++代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size() / 2];
    }
};

这种思路可以再次优化

基于快排的思想找中位数，如果n/2位置的元素恰好是中位数，则说明该元素出现的次数超过数组长度的一半 O(n)

参考文献

https://www.acwing.com/solution/content/1396/

算法三

划重点敲黑板

如果数组中存在一个数x的出现次数超过一半，那么任意删除两个不相同的数，x的出现仍然超过一半

用两个迭代器分别指向头和尾，如果两者不同，则进行删除，并更新尾部迭代器位置；否则更新头部迭代器位置；最终结果就是nums[0]；

C++代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        for (vector<int>::iterator it1 = nums.begin(),it2 = nums.end() - 1; it1 < it2; ){
            if (*it1 != *it2) {
                nums.erase(it1); --it2;//坑，vector删除后begin不会动，end会动
                nums.erase(it2); --it2;
            }
            else it1++;
        }
        return *nums.begin();//或者nums[0]
    }
};