数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
（一）哈希表法：
时间效率：O(n)
空间效率：O(n)
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array==null) return 0; if(array.length==0) return 0; int len=array.length/2; int[][] index=new int[10][1]; for(int i=0;i<array.length;i++) { index[array[i]][0]++; } for(int i=0;i<10;i++) { if(index[i][0]>len) return i; } return 0; } }（二）候选法:最佳解法
如果数组中存在一个数字的出现次数超过数组长度的一半，那么它的出现次数肯定比其他数字出现次数之和还要大
从头开始遍历数组，并记录数字和次数，当当前次数为0时，则令当前次数为1并记录数字，否则若数字相同则次数加1，数字不同则次数减1，要找的数字肯定是最后一次把次数设为1时对应的数字，但还需要进行验证，例如1 3 5 7 9最后一次将次数设为1时对应的数字是9，但其出现次数并没有超过数组长度的一半
时间效率：O(n)
空间效率：O(1)
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array==null) return 0; if(array.length==0) return 0; int sum=1; int num=array[0]; for(int i=1;i<array.length;i++) { if(sum==0) { num=array[i]; sum=1; } if(array[i]==num) sum++; else sum--; } //验证 sum=0; for(int i=0;i<array.length;i++) { if(array[i]==num) sum++; } if(sum>array.length/2) return num; else return 0; } }（三）排序法
基于快速排序
只能在允许改变数组的情况使用
如果数组中存在一个数字的出现次数超过数组长度的一半，那么它肯定位于排序后数组的中间
时间复杂度：O(nlogn)
空间复杂度：O(1)
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array==null) return -1; if(array.length==0) return -1; int mid=(array.length-1)/2; int start=0; int end=array.length-1; int index=findIndex(array,start,end); while(index!=mid) { if(index>mid) index=findIndex(array,start,index-1); else index=findIndex(array,index+1,end); } int num=array[mid]; int sum=0; //验证 for(int i=0;i<array.length;i++) { if(array[i]==num) sum++; } if(sum>array.length/2) return num; else return 0; } public int findIndex(int[] array,int start,int end) { if(array==null||array.length==0||start>end) return -1; int num=array[start];//不要将start写成0 int i=start; int j=end; while(i<j) { while(array[j]>=num&&i<j)//不要漏掉等号 j--; while(array[i]<=num&&i<j) i++; if(i<j) { int temp=array[i]; array[i]=array[j]; array[j]=temp; } } array[start]=array[i]; array[i]=num; return i; } }
扩展：
有O(n)的时间复杂度的算法可以得到数组中任意第k大的数字
public class Test { public static void main(String[] args) { int[] array= {1,3,6,8,2,4,90,34,56,100}; int k=1; System.out.println(get(k-1,array)); } //时间复杂度为O(nlogn) public static int get(int k,int[] array) { if(array==null||array.length==0||k<0) return -1; int start=0; int end=array.length-1; int index=findIndex(array,start,end); while(index!=k) { if(index>k) index=findIndex(array,start,index-1); else if(index<k) index=findIndex(array,index+1,end); } return array[k]; } //进行一次快速排序，返回首元素位于排序后的数组中的位置，时间复杂度为O(n) public static int findIndex(int[] array,int start,int end) { if(array==null||array.length==0) return -1; if(start>end) return -1; int num=array[start];//不要将start写成0 int i=start; int j=end; while(i<j) { while(i<j&&array[j]>=num) j--; while(i<j&&array[i]<=num) i++; if(i<j) { int temp=array[i]; array[i]=array[j]; array[j]=temp; } } array[start]=array[i];//不要将start写成0 array[i]=num; return i; } }
