题目要求
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。
思考题：
假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？ 样例 输入：[1,2,1,1,3]
输出：1
解题思路
public int moreThanHalfNum_Solution(int[] nums
) {
int con
=0,val
=nums
[0];
for(int i
=0; i
<nums
.length
; i
++) {
if(nums
[i
]==val
) con
++;
else{
con
--;
if(con
==-1) {
val
=nums
[i
];
con
=1;
}
}
}
return val
;
}
为什么最后的val就是答案呢？
我们使用反证法，假设val 不是超过一般的数字那么不等于他的值的个数肯定超过他，也就是说它对应的个数con肯定会被减到-1。所有val就是最后的答案。 思路很抽象建议自己写几个数组按照代码的思路，走几遍。
