题解 | #数组中出现次数超过一半的数字#

class Solution { //时间复杂度为o(n)，说明排序是不行的 //排序思想，出现最多的数字一定是在中间的，然后检测中间的数字就可以了

public: int MoreThanHalfNum_Solution(vector numbers) { int number = numbers[0];//找一个哨兵 int time = 1;//表示抵消的次数,也就是number出现的次数，目前的number出现了一次，如果 //time变成0了说明这个number被抵消过了，如果time++了说明遇到了和自己一样的，要多抵消 //一次才可以算是完全抵消完了 for(int i = 1; i<numbers.size(); ++i) { if(time == 0) { number = numbers[i];//这里说明我之前的那个number已经被抵消过一次了 //我要再换下一个没有被低效的继续来 time = 1; } else if(number == numbers[i]) { time++; } else { time--; } } return number; } };