- 给定一个无序的数组,请查找他们的中位数,比如用于统计公司所有人员工资的中位数,我们都知道对于实际情况来说平均数可能不如中位数来的贴近,
- 比如很多时候的"被平均",去年国家统计局的人均居住面积40平方米,你跟两马的资产平均过百亿,在看到手中的馒头,他是不是更香了呢?闲话少说,开始干活!
分析
- 首先应该想到的是对其排序,使用快排,时间复杂度O(nlogn),然后取中位数即可
- 但是如果对时间复杂度有要求呢? 或者不能使用完全排序!这个时候我们应该怎么办呢?
- 在网上看到很多这方面的分析,但是很少有能够跑的通的代码,这里就完善一下,直接运行即可
使用快排思想
- 快排是每次取一个参考值 X ,然后使用两个指针i , j 从前后跟参考值比较,首先也是必须从后面j开始遍历,如果 j 的值小于等于 X ,则在从 i 开始遍历找到那个大于X的,交换i , j 值,直到所有 大于X均在下标 i 右边, 小于等于 X均在 i左边
- 之所以使用 arr[j] <= X ,是为了处理对于偶数的中位数是 (n - 1) / 2 和 n / 2的问题,如果我们找到了n /2则直接找它前面最大的那个数字即为另一个中位数,对两者取平均即可
- 对于奇数来说,就不直接去 n / 2 下标即可
-
注意: 这个问题一定要注意区分数组的奇偶性: 代码如下,都有标注
/**
* 给定一个无续数组,查找他的中位数 : 时间复杂度尽可能低
* 思路: 对于中位数查找分两种情况
* 1. 数组长度为奇数,中位数下标为 n / 2
* 2. 数组长度为偶数,中位数为:下标 (n - 1) / 2 同 n / 2 下标数据之和 除以 2
*/
/**
*
* @param nums
* @param n : 数组nums的长度
* @return
*/
public int getMidNum(int[] nums , int n){
if (n == 0) return 0 ;
//采用快排的思想,每次选择一个数据作为基准,然后通过其下标跟中位数比较,这样每次都可以排除一半的数据(情况好的情况下)
int low = 0 ;
int high = n - 1 ;
int mid = n / 2 ; //mid1 肯定大于mid2的 , 且无论 奇偶性,mid1都是一致的,只是奇数没有mid2的求解了
int mid2 = (n - 1) / 2 ; //数组长度为偶数是另一个中位数的值
//首先根据快排思想获得选中的基准数据所在位置
int div = sortNum(nums , low , high) ;
int div2 = -1 ; //偶数长度时另外一个较小的中位数,奇数不用此值
int midNum2 = Integer.MIN_VALUE ; //偶数型时较小的那个中位数的值,默认最小
while (div != mid){ //如果下标不为中位数则由两种情况
if (div > mid){ //肯定也是大于mid2的,因此mid跟mid2都在其左边寻找
div = sortNum(nums , 0 , div - 1) ;
}else { //否则:div < mid,但是对于偶数来说可能div == mid2哦
if ((n & 1) == 0 && div == mid2){ //偶数且值正好相等
mid2 = div ; //偶数情况下,找到了那个较小的中位数
midNum2 = nums[div] ; //赋值否则可能更改
}
div = sortNum(nums , div + 1 , high) ; //在div右侧寻找
}
}
//上次循环完成以后div的值即为mid所在位置:依然需要判断奇偶性
int midNum = nums[mid];
if ((n & 1) == 0 ){ //偶数
if (div2 == -1){//没有找到div2
for (int i = 0; i < mid; i++) { //注意: 在下标mid左边的全部是小于等于该值的
midNum2 = Math.max(nums[i] , midNum2); //找到他们中最大的即可
}
}
return (midNum + midNum2) / 2 ;
}else{ //奇数
return midNum ;
}
}
/**
* 使用快排思想对其进行排序: 每次从右边开始遍历找到小于当前基准的值,然后遍历左边,找到大于当前基准的值,直到相遇
* @param nums
* @param : 比较基准的下标,这里使用首位进行比较
* @param low : 起始坐标
* @param high : 终点坐标
*/
private int sortNum(int[] nums , int low , int high){
int keyIndex = low ; //以最左边
while (low < high){
while (low < high && nums[high] > nums[keyIndex]){ //所有小于等于keyIntex的值都在其左边,为了对偶数排序方便
high-- ;
}
while (low < high && nums[low] <= nums[keyIndex]){
low++;
}
if (low < high){
//交换low跟high的值
int temp = nums[low] ;
nums[low] = nums[high];
nums[high] = temp ;
}
}
int temp = nums[keyIndex] ;
nums[keyIndex] = nums[low] ;
nums[low] = temp ;
return low ;
}
使用最小堆思想
- 处理这种问题,我们应该常想到的是最小堆,这样只需要取堆顶元素即可:
- 如果你对线程池了解的情况下,肯定知道优先级队列 PriorityQueue,它就是使用数组实现的堆,关于这个数据结构,我会单独开个文章写的:这里简单说一下他的结构
- 使用可扩展的数组实现的最小堆,特点是堆顶是下标为0的元素,数组中没有空余的,对于下标为i的元素,其两个左右节点数据大小都大于它,并且左孩子在 arr[i * 2 + 1] , 右孩子在arr[i * 2 + 2],父节点是 arr[(i -1)/2]
- 每次新加都是加入到数组尾部,然后在根据大小关系调节数组,删除元素也是
- 注意: priorityQueue默认使用最大堆(堆顶是最大值元素),这里我们传入自己的compartor比较器即可,注意维护堆元素始终为 (n + 2) / 2
/**
* 最小顶堆的大小依然分成奇数,偶数区分
* 奇数: 个数为5 ,则中位数为 3 存储三个数据3, 4, 5 => 堆的数组长度为:(n + 2) / 2
* 偶数: 个数为 6, 则中位数为 3, 4 => 由于是最小堆,我们需要从 3->6 四个数据因此设置为(n + 2) / 2
* @param arr
* @param n
* @return
*/
public int getMinHeap(int[] arr , int n){
if (n == 0) return 0 ;
int heapLen = (n + 2) / 2 ;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(heapLen, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i1 - i2;
}
});
for (int i = 0; i < n; i++) {
if (priorityQueue.size() < heapLen){
priorityQueue.add(arr[i]);
}else{ //超过了最大堆,这个时候就不要添加了,否则堆会扩容
//只是拿到堆顶元素,这个是目前堆中最小的那个数据,并不会真正弹出
if (priorityQueue.peek() < arr[i]){ //弹出堆顶元素,并加入arr[i]重新排序
priorityQueue.poll();
priorityQueue.add(arr[i]);
}
}
}
if ((n & 1) == 0){ //偶数,弹出两个值进行比较
Integer mid1 = priorityQueue.poll();
Integer mid2 = priorityQueue.peek();//只拿到值就不要后续在更新数据了
return (mid1 + mid2) /2 ;
}else{
return priorityQueue.peek() ;
}
}
给定两个有序数组查找中位数
- 题目:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
- leetCode中标注的为困难,通常由于有序,首先想到的解题思路为:
- 使用两个指针 i , j分别指向两个数组,比较他们的值,依次移动较小的那个,直到 i + j = (k -1)/ 2,分成奇数偶数求解即可,时间复杂度为: O(m+n),而题目要求的是O(log(m+n))
使用二分法求解
- 对于log(m+n)时间复杂度,首要使用的是二分法求解方式,思路是对于 中位数k = (m + n) / 2,可以分别在两个数组中查询 k / 2的位置数据,比较他们的值,较小的那个肯定不是中位数所在的范围,直接舍弃,同时查询数量k - 舍弃长度,在递归比较剩下的数据即可
/**
* 寻找两个有序数组的中位数
* 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
*
* 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
*
* 你可以假设 nums1 和 nums2 不会同时为空。
*
* 思路1: 如果不考虑时间复杂度: 可以使用两个指针i , j分别从m , n 遍历,每次找到他们之间最小值,移动指针并 num ++ ,直到 num = (m + n) / 2即可,这个不满足时间复杂度
* 思路2: 由于要求时间复杂度为O(log(m + n), 一般都是二分查找的复杂度,对于此题我们也可以使用)
* 具体方法是,找到当前要找的值 K 的一半 K/2在m和n中的位置,比较他们的大小,去除掉较小的那个,如果一致,去除掉相对较小的那个长度l,同时查找的也是 (k - l ) / 2 在比较剩下的即可
*
*/
public int getDoubleArr(int[] nums1 , int[] nums2){
int m = nums1.length ;
int n = nums2.length ;
//根据奇偶性统一了
int left = (m + n + 1) / 2 ;
int right = (m + n + 2) / 2 ;
/**
* 根据上式,我们需要找到的是其实是left就可以了,对于偶数为我们直接在遍历一个就行了
* nums1是从0--> m- 1 取值的
* nums2 是从0--> n - 1 取值的
*/
return(getReallyArr(nums1 , 0 , m - 1 , nums2 , 0 , n - 1 , left) +
getReallyArr(nums1 , 0 , m - 1 , nums2 , 0 , n - 1 , right) ) / 2;
}
private int getReallyArr(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1 ;
int len2 = end2 - start2 + 1 ;
//转换一次,不用比较两个数组的大小,固定比如nums1肯定是最大的那个,如果不是就转化他们,直到他们是
if (len1 < len2) return getReallyArr(nums2 , start2 , end2 , nums1 , start1 , end1 , k);
//这下方所有解答方式只有一种可能len1 > len2了
if (len2 == 0) return nums1[start1 + k - 1] ; //len2为较小的那个数组如果为空,则直接从nums1中start取到k
//否则len1 跟len2都不为空
if (k == 1) return Math.min(nums1[start1] , nums2[start2]);
//比较i , j之间最大的那个下标,当前删除的个数是需要减去start的
int i = start1 + Math.min(len1 , k / 2) - 1 ;
int j = start2 + Math.min(len2 , k / 2) - 1 ;
if (nums1[i] >= nums2[j]){
//去掉nums2的
return getReallyArr(nums1 , start1 , end1 , nums2 , j + 1 , end2, k - (j - start2 + 1)) ; //当前排除的数据为当前下标 - 上一个已经排除的start + 1
}else{
return getReallyArr(nums1 , i + 1 , end1 , nums2 ,start2 , end2 , k - (i - start1 + 1)) ;
}
}
