给定两个升序的数组 arr1 和 arr2 ,求两个数组合并后的下中位数
注意:下中位数指在两个数组的数个数在偶数时取更小的
数据范围:两个数组的长度都满足 ,数组中的所有值都满足
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param arr1 int整型一维数组 * @param arr2 int整型一维数组 * @return int整型 */ public int getUpMedian (int[] arr1, int[] arr2) { // write code here int index = (arr1.length + arr2.length) / 2; if((arr1.length + arr2.length) % 2 == 0) index--; int p1 = 0, p2 = 0, p = 0; while(p1 < arr1.length && p2 < arr2.length){ if(arr1[p1] <= arr2[p2]){ if(p == index) return arr1[p1]; p1++; }else{ if(p == index) return arr2[p2]; p2++; } p++; } while(p1 < arr1.length){ if(p == index) return arr1[p1]; p1++; p++; } while(p2 < arr2.length){ if(p == index) return arr2[p2]; p2++; p++; } return -1; } }因此我们可以复用上一题“NC251 多数组第K小数”的算法流程,找到第中间小的数就可以了,时间复杂度可以达到O(logn)级别。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param arr1 int整型一维数组 * @param arr2 int整型一维数组 * @return int整型 */ public int getUpMedian (int[] arr1, int[] arr2) { // write code here int index = (arr1.length + arr2.length) >>> 1; if(((arr1.length + arr2.length) & 1) == 0) index--; return findKthNum(arr1, arr2, index + 1); // 注意调用此函数时没有第0小的数,rank序从1开始 } public int findKthNum (int[] arr1, int[] arr2, int kth) { int[] longs = arr1.length >= arr2.length ? arr1 : arr2; int[] shorts = arr1.length < arr2.length ? arr1 : arr2; int l = longs.length; int s = shorts.length; if(kth <= s){ return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1); } if(kth > l){ if(shorts[kth - l - 1] >= longs[l - 1]){ return shorts[kth - l - 1]; } if(longs[kth - s - 1] >= shorts[s - 1]){ return longs[kth - s - 1]; } return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1); } if(longs[kth - s - 1] >= shorts[s - 1]){ return longs[kth - s - 1]; } return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1); } public int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2) { int mid1 = 0; int mid2 = 0; int offset = 0; while(s1 < e1){ mid1 = (s1 + e1) / 2; mid2 = (s2 + e2) / 2; offset = ((e1 - s1 + 1) & 1) ^ 1; if(a1[mid1] > a2[mid2]){ e1 = mid1; s2 = mid2 + offset; }else if (a1[mid1] < a2[mid2]){ s1 = mid1 + offset; e2 = mid2; }else{ return a1[mid1]; } } return Math.min(a1[s1], a2[s2]); } }不仅时间复杂度指标上比直接归并更优,经过测试,直接提交后的运行时间也确实缩短了。
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param arr1 int整型一维数组 * @param arr2 int整型一维数组 * @return int整型 */ func getUpMedian( arr1 []int , arr2 []int ) int { var target,n,m int n,m=len(arr1),len(arr2) if (n+m)%2==0{ target=(n+m)/2-1 }else{ target=(n+m)/2 } var x int for target>=0&&n>0&&m>0{ if arr1[0]>arr2[0]{ x=arr2[0] arr2=arr2[1:] m-- }else{ x=arr1[0] arr1=arr1[1:] n-- } target-- if target<0{ return x } } if n>0{ return arr1[target] } return arr2[target] }
import java.util.*; public class Solution { public int getUpMedian(int[] arr1, int[] arr2) { //k为中位数在两个数组中所处的位置,从1开始计数,由升序排序的第几个数 // 需使用Math.ceil()或直接加+1向上取整 int k = (arr1.length + arr2.length + 1) / 2; int m = 0, n = 0; int len1 = arr1.length, len2 = arr2.length; int ret = -1; while (m + n < k) { if (m < len1 && n < len2) { if (arr1 [m] < arr2 [n]) { ret = arr1 [m++]; } else { ret = arr2 [n++]; } } else if (m < len1) { return arr1 [k - n - 1]; } else { return arr2 [k - m - 1]; } } return ret; } }