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);
	}
}