class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
int flag=nums[0];//用以记录当前个数最多的元素
int cnt=1;//用以记录当前个数最多的元素还剩几个
for(int i=1;i<nums.size();i++){
if(nums[i]!=flag)
cnt--;//不同就减一
else
cnt++;//相同就加一
if(cnt==0){//如果等于0了,就更新当前个数最多的元素
flag=nums[i];
cnt++;
}
}
return flag;
}
};
能在数组中出现超过一半的数字,那么这个数组的中间值必定是他,直接判断中间值是否出现了一半的次数,如果超过了就是,如果没有出现这么多就没有超过一半的次数的数字(先排序)
无规律的序列,排序的最快时间复杂度要o(nlogn)