【牛客网】JZ39 数组中出现次数超过一半的数字

题目

思路

思路1

将数组排序,再保证有结果的情况下,此时数组中间的数字就是想要的结果

思路2

在保证有结果的情况下,此时数组的的众数是数组长度的一半以上
所以我们可以通过抵消的做法来找到最终的结果

我们可以从头遍历这个数组,如果两个数不相同,则消去这两个数,最坏的情况下,最后就剩下一个数就是我们想要的结果

代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型一维数组 * @return int整型*/public int MoreThanHalfNum_Solution (int[] numbers) {// write code hereint result = numbers[0];int times = 1;//result用来记录此时结果的数字//times用来记录出现的次数//默认result初始值为数组第一个元素,times的值为1//遍历数组for(int i = 1; i < numbers.length; i++){//如果此时次数不为0,说明这个数字没有消除完if(times != 0){//如果此时两个相邻的数不同,则消去这个数,即times--if(numbers[i] != result){times--;//反之则说明两个数相同,此时这个数出现的次数又+1,times++}else{times++;}//如果此时times为0,则说明这个数字消除结束了}else{//此时重新制定result和timesresult = numbers[i];times = 1;}}return result;}
}