题目描述

解法来自yxc
只是加了注释方便自己这样基础薄弱的人看一下

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

1.考虑需要遍历整个数组；
2.考虑我可以设定一个计数器，记录重复的那个数的个数，所以有了cont;另外我需要输出重复的那个数，所以有了val
3.数组中的数，我们可以假设为x。
开始遍历第一个x,此时计数器+1,cont=1;val=x。
如果下一个数还是x,那么val还是等于x,cont=2;
假设第三个数为y，那么cont此时等于2-1=1，val还是x,
如果第四个数还是z,那么cont此时等于1-1=0；此时符合开头if(!cont) 这个条件，那么val变成了z的值；
就是这样通过计数来确定val的值，最后肯定留下了重复的那个数，因为他出现的次数过一半

时间复杂度分析：blablabla

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cont =0, val= 0;
        //循环遍历数组nums
        for(auto x:nums)
        {
            if(!cont) val =x , cont =1;//如果cont 计数器为零 val等于数组中的x,计数器为1；
            else//计数器cont不为零的时候
            {
                if(x==val) cont++;//如果说x的值等于val当前那么就++；
                //x不等于val当前值，计数器减，但是val还是不变的，除非cont变成了0了，再遍历下一个的时候val变成了下一个x,计数器为1
                else cont--;
            }

        }
        return val;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla