题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路
1，第一种，超过一半的数必然出现在递增数组中间，先排序，然后统计中间值次数
2，第二种，遍历每一个数出现的次数，放到map里，然后用次数和len/2比较
3，第三种，利用数组的特性，超过一半的数出现的总次数比其它所有数出现总次数还多，这样我们在遍历数组的时候第一个值为result,次数为1，遇到相同的次数加1，遇到不同的减1，次数为0时，重复上述过程，最后得出的数即是持有股份最多的，不一定超过一半，然后我们在遍历统计它出现的次数，超过一半就是。
代码实现
/** * */ package 数组; import java.util.Arrays; import java.util.HashMap; /** * <p> * Title:MoreThanHalfNum * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月25日 下午5:13:34 */ public class MoreThanHalfNum { // ===========================================================排序取中间值，时间复杂度nlogn public static int moreThanHalfNumSort(int[] array) { if (array == null || array.length < 1) { return -1; } int len = array.length; Arrays.sort(array); int num = array[len / 2]; int count = 0; for (int i = 0; i < array.length; i++) { if (array[i] == num) { count++; } } if (count * 2 > len) { return num; } else { return 0; } } // ============================================================存放到hashmap里，时间复杂度为O（n）,空间复杂度为O（n） public static int moreThanHalfNum(int[] array) { if (array == null || array.length < 1) { return -1; } HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // 给数组中所有数字标记出现次数 for (int i = 0; i < array.length; i++) { if (map.containsKey(array[i])) { map.put(array[i], map.get(array[i]) + 1); } else { map.put(array[i], 1); } } int len = array.length; for (int i = 0; i < map.size(); i++) { if (map.get(array[i]) > len / 2) { return array[i]; } } return 0; } // ============================================================根据数组特点，时间复杂度O（n） public static int moreThanHalfNumSuper(int[] array) { if (array == null || array.length < 1) { return -1; } int len = array.length; int count = 1; int result = array[0]; for (int i = 1; i < array.length; i++) { if (count == 0) { result = array[i]; count = 1; } if (result == array[i]) { count++; } else { count--; } } // 最后持有count值的result可能就是超过一半的（{ 1, 2, 3, 2, 2, 2, 5, 4, 2 // }，也有可能小于一半{1,2，2,3,4}，但其是唯一候选人，股份最大的） // 遍历次数，如果次数超过一半，则说明是 count = 0; for (int i = 0; i < array.length; i++) { if (array[i] == result) { count++; } } if (count * 2 > len) { return result; } else { return 0; } } public static void main(String[] args) { int[] array = { 1, 2, 3, 2, 2, 2, 5, 4, 2 }; System.out.println(moreThanHalfNum(array)); System.out.println(moreThanHalfNumSort(array)); } }
