给定两个升序的数组 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]); } }不仅时间复杂度指标上比直接归并更优,经过测试,直接提交后的运行时间也确实缩短了。