数组中出现次数超过一半的数字Java
数组中出现次数超过一半的数字
http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
采用阵地攻守的思想:
1,在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。
2,当我们遍历到下一个数字的时候,如果下一个数字和当前我们保存的数字相同,则次数加 1;
如果和当前我们保存的数字不同,则次数减 1;
当次数减到 0 的时候,我们将保存的数字改为当前遍历所处的位置,并将次数更改为 1。
3,最后当times>1,说明当前的num出现的次数超过一半
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0){ return 0; } int times = 1; int num = array[0]; for(int i=0; i<array.length;i++){ if(num == array[i]){ times++; }else{ times --; if(times == 0){ num = array[i]; times =1; } } } if(times>1){ return num; }else{ return 0; } }
}