package arrays;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目:求数组中超过一半的数字
 *
 * @Author Gavin
 * @date 2021年12月23日 22:05
 */
public class array_8 {
 /**
 * 第一种方法:借助一个hashmap来存储每个数字出现的次数,然后返回
 * 最大的次数的那个值就行,因为题目要求是超过一半的数字,出现次数最大
 * 的那个数就是超过一半的数字
 */
 //Time:O(n) Space:O(n)
 public static int solution_1(int[] array){
 Map<Integer,Integer> map=new HashMap<>();
 int max=0,count=0;
 for (int i = 0; i < array.length; i++) {
 //首先获取这个值对应的次数然后+1
 int preCount=map.getOrDefault(array[i],0)+1;
 map.put(array[i],preCount);
 if(preCount>count){
 max=i;
 count=preCount;
 }
 }
 return max;
 }
 /**
 * 第二种方法:采用摩尔投票法
 * 采用一个计数器,然后对出现的相同的数字进行加1,出现不同的数字就减1,
 * 这样最后留下的数字肯定就是超过一半的这个数字了
 * 比如: 1 2 1
 * 开始指向1,计数器+1后就为1
 * 然后指向2,此时不同,计数器-1
 * 然后指向1,此时计数器重新开始计算,又加1
 */
 //Time:O(n) Space:O(1)
 public static int solution_2(int[] array){
 int count=1,num=array[0];
 for (int i = 1; i < array.length; i++) {
 int pre=array[i];
 if(count==0){//关键点如果count为0就重新开始下一个计数了
 num=pre;
 count=1;
 continue;
 }
 if(num==pre)count++;
 else{
 count--;
 }
 }
 return num;
 }
}