题目:一个无序数组中有一个数出现的次数超过数组长度的一半,找出该值。如{1,2,3,2,4,2,5,2},值为2。
思想:如果数组是有序的,那么出现次数超过一半的值一定是它的中位数,因此一种方法就是全排序,然后中间的那个数就是要找的值。
还有一种方法就是将上述问题转化为找中位数的问题。这时候就可以用快排的思想了,不断的左右排序,直到找到基准值所在的位置是n/2,这时候左右达到平衡。如果基准值小于n/2,那么中位数一定在右边,于是继续从右边找,如果大于n/2,那么中位数一定在左边,那么就在左边找,如此递归,直到找到为止。总的思想还是快排。
public int findUsingQuickSort(int[] arr, int start, int end){
int low = start;
int high = end;
int key = arr[start];
while(low < hight){
while(low<high && arr[high]>key){
high--;
}
arr[low]=arr[high];
while(low<high && arr[low]<key){
low++;
}
arr[high]=arr[low];
}
arr[low] = key;
if(low==(arr.length-1)/2){
return arr[(arr.lenght-1)/2]
}else if(low<(arr.length-1)/2)
return findUsingQuickSort(arr, low+1, end);
}else if(low > (arr.lenght-1)/2){
return findUsingQuickSort(arr, start, low-1);
}
return -1;
}
网友评论