题目:利用
快排
思想求一个无序
数组的中位数
对于一个有序数组arr
来说:
- 如果数组长度为奇数,中位数为中间的那个数,即
arr[arr.length/2]
- 如果数组长度为偶数,中位数为中间的两个数的平均值,即
(arr[length/2] + arr[length/2-1]) / 2
那么对于一个无序数组来说,应该如何求它的中位数 ?
这个问题可以抽象化为寻找第k
大的数,具体到寻找中位数,可分为两种情况:
- 如果数组长度为奇数,即为寻找第
arr.length/2
大的数; - 如果为偶数,则为分别寻找第
arr.length/2+1
和第arr.length/2
大的数,然后求其平均值。
我们可以使用快排思想快速找中位数,即先挑选一个数作为标准(
pivot
),以该元素为支点,将数组划分为两部分。快排每排完一轮之后左侧都是比它小的元素,右侧都是比它大的元素,那么支点的index(假设为N-1)
即为第N
大的数。当N== K
,我们就找到了第K
大的数;当N > K
时, 第K
大的数在[0,N-1]
范围内;当N < K
时,第K
大的数在[N+1,n-1]
(n为数组长度)范围内,利用递归即可找到第K
大的数。
注意:这里第
k
大的数,是下标为k-1
的值,即arr[k-1]
Java 实现如下:
/**
* 利用快排思想求无序数组中位数
* @Author Hory
* @Date 2020/9/8
*/
public class Solution {
/**
* 寻找无序数组第k大的数,其实就是找排序后的数组的 arr[k-1]
* 这里用到了递归
* 明确函数意义:该方法实现了找到第k大的数,该方法没有返回值,通过不断调整数组,最终使得第k大的值位于索引k-1
* @param arr
* @param k
* @param start
* @param end
* @return
*/
private static void selectKthNum(int[] arr, int k, int start, int end){
if(arr == null || k < 0 || start >= end) return;
int left = start;
int right = end;
int pivot = arr[start];
while(left < right){
while(left < right && arr[right] >= pivot) right--;
arr[left] = arr[right];
while(left < right && arr[left] <= pivot) left++;
arr[right] = arr[left];
}
arr[left] = pivot;
if(left == k) return;
else if(left < k) selectKthNum(arr,k,left+1,end);
else selectKthNum(arr,k,start,left-1);
}
/**
* @param arr
* @return
*/
public static double findMedian(int[] arr){
if(arr.length <= 0) return -1;
int length = arr.length;
if(length % 2 == 1) { // 如果数组长度为奇数,只需返回中间的数字即可
selectKthNum(arr,length/2,0,length-1);
return arr[(length)/2];
}else { //如果数组长度为偶数,返回中间两个数字的平均值
selectKthNum(arr,length/2-1,0,length-1);
selectKthNum(arr,length/2,0,length-1);
return (arr[length/2] + arr[length/2-1])/2.0;
}
}
}