题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
package alex.suda.jzOffer; import java.util.HashMap; import java.util.Iterator; import java.util.Map.Entry; import java.util.Scanner; public class MoreThanHalfNum_Solution { /** * @param args */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = scanner.nextInt(); } System.out.println(moreThanHalfNum_Solution(array)); } } //方法1：基于Partition函数的o(n)算法 public static int moreThanHalfNum_Solution(int[] array) { int len = array.length; int mid = len / 2; int low = 0; int high = len - 1; int index = partition(array, low, high);// 返回的位置 while (index != mid) { if (index > mid) { high = index - 1; index = partition(array, low, high); } else { low = index + 1; index = partition(array, low, high); } } int result = array[mid]; int times = 0; for (int i = 0; i < len; i++) { if (array[i] == result) { times++; } } if (times * 2 <= len) { return 0; } else { return array[mid]; } } public static int partition(int[] a, int low, int high) { int key = a[low]; while (low < high) { while (low < high && a[high] > key) { high--; } if (low < high) { a[low] = a[high]; low++; } while (low < high && a[low] <= key) { low++; } if (low < high) { a[high] = a[low]; high--; } } a[low] = key; return low; } // 方法2 用hashmap来做 public static int moreThanHalfNum_Solution1(int[] array) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int len = array.length; for (int i = 0; i < len; i++) { if (!map.containsKey(array[i])) { map.put(array[i], 1); } else { map.put(array[i], map.get(array[i]) + 1); } } Iterator<Entry<Integer, Integer>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Entry<Integer, Integer> entry = iterator.next(); if (entry.getValue() > len / 2) { return entry.getKey(); } } return 0; } // 方法3：根据数组特点 O(n) public static int moreThanHalfNum_Solution2(int[] array) { int len = array.length; int result = array[0]; int times = 1; for (int i = 1; i < len; i++) { if(times == 0){ result = array[i]; times = 1; } else if(array[i] == result){ times++; } else{ times--; } } int count = 0; for(int i=0;i<len;i++){ if(array[i] == result){ count++; } } if(count * 2 <= len){ return 0; } else{ return result; } } }