剑指Offer 数组中出现次数超过一半的数字

import java.util.HashMap;
import java.util.Map;/*** 数组中出现次数超过一半的数字** 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。* 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。*/public class JZ028MoreThanHalfNum {/*** HashMap存储* @param a* @return*/public int MoreThanHalfNum_Solution(int [] a) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < a.length; i++) {if (!map.containsKey(a[i])) {map.put(a[i], 1);} else {map.put(a[i], map.get(a[i]) + 1);}}for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() >= (a.length / 2 + 1)) {return entry.getKey();}}return 0;}/*** 候选法* @param a* @return*/public int MoreThanHalfNum_Solution2(int [] a) {int cond = -1;int cnt = 0;for (int i = 0; i < a.length; i++) {if (cnt == 0) {cond = a[i];cnt++;} else {if (cond == a[i]) {cnt++;} else {cnt--;}}}cnt = 0;for (int num : a) {if (cond == num) {cnt++;}}if (cnt >= (a.length / 2 + 1)) {return cnt;}return 0;}}