java-74-数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字
public class OcuppyMoreThanHalf {/** * Q74 数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字 * two solutions: * 1.O(n) * see <beauty of coding>--每次删除两个不同的数字，不改变数组的特性 * 2.O(nlogn) * 排序。中间那个元素就是所求 */public static void main(String[] args) {int[] a={4,3,4,2,4,5,4,4};int result=find(a);System.out.println(result);result=findAfterSort(a);System.out.println(result);}public static int find(int[] a){if(a==null||a.length==0){return -1;}int len=a.length;int candidate=a[0];int times=1;for(int i=1;i<len;i++){if(candidate!=a[i]){times--;if(times==0){candidate=a[i];times=1;}}else{times++;}}return candidate;}public static int findAfterSort(int[] a){if(a==null||a.length==0){return -1;}myQuickSort(a,0,a.length-1);int midIndex=a.length/2;return a[midIndex];}public static void myQuickSort(int[] a,int start,int end){if(start>=end){return;}boolean flag=false;int s=start,e=end;while(s<e){if(a[s]>a[e]){Helper.swap(a,s,e);flag=true;}if(flag){s++;}else{e--;}}myQuickSort(a,start,s-1);myQuickSort(a,e+1,end);}}