多数组中位数

[编程题]多数组中位数

热度指数：1333 时间限制：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)

小谷围做题家

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

发表于 2023-03-15 00:18:19 回复(0)

子沐728592488

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr1 int整型一维数组
* @param arr1Len int arr1数组长度
* @param arr2 int整型一维数组
* @param arr2Len int arr2数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int getUpMedian(int* arr1, int arr1Len, int* arr2, int arr2Len ) {
// write code here
int maxCount = (arr1Len + arr2Len + 1) / 2;
int ret = 0;
int i = 0;
int j = 0;

for (int count = 0; count < maxCount; count++) {
if (i < arr1Len) {
if (j < arr2Len) {
if (arr1[i] < arr2[j]) {
ret = arr1[i++];
} else {
ret = arr2[j++];
}
} else {
ret = arr1[i++];
}
} else {
ret = arr2[j++];
}
}

return ret;
}

发表于 2022-07-10 13:07:31 回复(0)

王②虎

双指针模拟

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

编辑于 2022-01-14 19:25:36 回复(0)