剑指offer39

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

1. HashMap:HashMap<Integer,Integer> hashmap=new HashMap<>()

• hashmap.put(i,j):添加元素key=i对应value为j
• hashmap.get(i):访问i对应的value,若不存在key则返回null，可以在初次插入用来判空
• for(Integer(key类型) i:hashmap.keySet()) hashmap.get(i)
• for(Integer(value类型) i:hashmap.values())
• containsKey()/containsValue() 容器含有对应的key值或者value则返回true,用来判空

2. 摩尔投票法，前a个数字的票数和为0，则剩余（n-a）个数的票数之和一定仍然>0(题目说明一定存在大于一半数量的数)，剩余数组的众数一定不变。vote==0时，当前的num值即为当前这一轮投票区间的众数。