[TOC]
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路一：利用map统计每个数字出现的次数
代码
import java.util.HashMap;import java.util.Map;public class Solution { public int MoreThanHalfNum_Solution(int [] array) { int num = 0; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); int len = array.length ; if(len == 0) return 0; for(int i = 0; i < len ;i++){ if(map.containsKey(array[i])){ int count = map.get(array[i]); ++count; map.put(array[i],count); }else{ map.put(array[i],1); } } for(Map.Entry<Integer,Integer> entry: map.entrySet()){ if(entry.getValue() > (len/2)){ num = entry.getKey(); } } return num; }}总结
- map的遍历方式
- 使用map存储出现次数的映射关系
- map.put(key,value)
思路二：先对数组进行排序，然后取出arr[n/2]
由于出现次数超过一半，那么最中间的数一定是那个出现次数超过一半的数，也就是中位数
我们先用排序算法对该数组排序，若用快速选择排序，时间复杂度为O(nlogn)
思路三：基于partition函数的O(n)的算法
我们知道快速排序中，每次划分都是基于partition函数返回的index作为划分点，使得数组左边的数小于arr[index],数组右边的数大于arr[index]
这里其实partition返回的index也就是数组arr中第k大数据的坐标索引
所以借鉴过来，本题需要求出现次数超过一半的数，那么实际上也就是中位数，即索引为n/2的数，
就等同于求第n/2大的数据
快速排序算法中我们是通过partition函数求出索引，本题我们是知道了索引，求具体的数据
那么我们就需要以n/2为基准，使得左边的数小于arr[n/2],右边的数大于arr[n/2]
实现
public class Solution { //检测无效输入，如果数字的次数不超过长度的一半 public boolean isValid(int[] arr,int numer){ int count = 0; for(int i = 0; i < arr.length; i++){ if(numer == arr[i]) count++; } if(count * 2 <= arr.length) return false; return true; } public void swap(int[] arr,int i,int j){ int temp = 0; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public int partition(int[] arr,int low,int high){ int base = arr[high]; int i = low - 1; for(int j =low; j < high; j++){ //注意这里是小于等于 if(arr[j] <= base){ i++; swap(arr,i,j); } } swap(arr,i + 1,high); return i+1; } public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length <= 0)return 0; int index = partition(array, 0, array.length - 1); int middle = (array.length - 1) >> 1; while (index != middle){ if(index < middle){ index = partition(array, index + 1, array.length - 1); }else { index = partition(array, 0, index - 1); } } boolean flg = isValid(array, array[middle]); if(!flg) return 0; return array[middle]; }}该思路的时间复杂度：平均时间复杂度为O(n * logn/2) = O(nlogn),如果一次性就能找到n/2的下标，那么时间复杂度可以达到o(n)
但是该算法的缺点在于修改了原数组
思路四：根据数组特点找出O（n）的算法
由于有个数字出现的次数超过数组长度的一半，那么也就是说它出现的次数比其他数字出现的次数之和还要多，如果我们将数组中的数字两两同或（相同为1，相异为0）那么两两抵消之后，最后只会剩下这个出现出现次数超过一半的数字，那么我们如何实现这个同或抵消的过程呢
首先我们需要保存当前正在读取的数，还有当前数字出现的次数，如果下一个数字和当前数字不相同，那么当前数字的次数就减1，
public class Solution { public boolean isValid(int[] arr,int numer){ int count = 0; for(int i = 0; i < arr.length; i++){ if(numer == arr[i]) count++; } if(count * 2 <= arr.length) return false; return true; } public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length <= 0) return 0; int cur = array[0]; int count = 1; int res = array[0];//初始化为array[0]有可能第一个数就是返回值 for(int i = 1; i < array.length; i++){ if(cur != array[i] ){ if(count != 0){ count--; }else { count = 1; res = array[i]; } cur = array[i]; }else { count++; } } boolean flg = isValid(array, res); if(!flg) return 0; return res; }}该算法的时间复杂度为：O(n)
参考
《剑指offer纪念版》