多数组中位数

[编程题]多数组中位数

热度指数：1335 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个升序的数组 arr1 和 arr2 ，求两个数组合并后的下中位数

注意：下中位数指在两个数组的数个数在偶数时取更小的

数据范围：两个数组的长度都满足 $1 \le n \le 10^6 \$ ，数组中的所有值都满足 $0 \le val \le 10^9 \$

示例1

输入

[1,2,3],[3,4,5]

输出

示例2

输入

[1,2,3],[4,5]

输出

算法知识视频讲解

Java

pein531

这个题用外排的方式实现是绝对可以解的，只是直接归并的时间复杂度比较高，面试场合下并不适合聊这个算法。

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]);
    }
}

不仅时间复杂度指标上比直接归并更优，经过测试，直接提交后的运行时间也确实缩短了。

编辑于 2021-12-21 11:36:45 回复(0)