数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。
思考题：
- 假设要求只能使用
的时间和额外
的空间，该怎么做呢？
样例
输入：[1,2,1,1,3]
输出：1
分析：
如果一个数大于一半，这个数最后的数量肯定大于其他所有数的数量之和。
class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
//如果一个数大于一半，这个数最后的数量肯定大于其他所有数的数量之和。
int count = 1, res = nums[0];
for(int i=1;i<nums.size();i++) {
if(res == nums[i]) count++;
else count--;
if(!count) res = nums[i], count = 1;
}
return res;
}
};
网友评论