题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
前几种方法,都有思考到,一个是sort方法,还有一个hashmap,但这些方法都不符合要求,空间不符合。
所以,下面的哈希法,是一种变种,更多是,通过一个 cond/cnt, 再叠加for循环,竞争上岗的。!
import java.util.*; public class Solution { /** * @param numbers int整型一维数组 * @return int整型 */ public int MoreThanHalfNum_Solution (int[] numbers) { int candiate = -1; int cnt =0; for(int i=0; i<numbers.length; i++) { if(cnt == 0) { //这里我刚开始是用candiate ==-1做比较的,但是,这种后面逻辑不能复用, // 比如 cnt-- 到0是,还要再重制candiate,而且还有多一次遍历,所以用了 // cnt ==0,复用逻辑,减少代码量 candiate = numbers[i]; cnt++; } else { if(candiate == numbers[i]) { cnt++; } else { cnt--; } } } return candiate; } }