题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
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; } };
难怪小公司那么挑剔，让你们这些大佬把位置拿了
