java-74-配列の中で一つの数字が出てくる回数は配列長の半分を超えています。この数字を探してください。
1616 ワード
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);
}
}