首页 > 试题广场 >

在两个长度相等的排序数组中找到上中位数

[编程题]在两个长度相等的排序数组中找到上中位数

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

给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。

上中位数：假设递增序列长度为n，为第n/2个数

数据范围： $1 \le n \le 10^5$ ， $0 \le arr_1,arr_2 \le 10^9$

要求：时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

进阶：时间复杂度为 $O(logN)$ ，空间复杂度为 $O(1)$

示例1

输入

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

输出

说明

总共有8个数，上中位数是第4小的数，所以返回3。

示例2

输入

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

输出

说明

总共有6个数，那么上中位数是第3小的数，所以返回2

示例3

输入

[1],[2]

输出

备注:

算法知识视频讲解

Java

蒋劲豪

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int findMedianinTwoSortedAray(int[] arr1, int[] arr2) {
        int[] arr3 = IntStream.concat(Arrays.stream(arr1), Arrays.stream(arr2)).toArray();
        Arrays.sort(arr3);
        return arr3[(arr3.length -1) >> 1];
    }
}

发表于 2024-04-27 09:52:38 回复(0)

Java

牛客781396821号

经典的双指针问题之一

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int result = 0;
        int length = arr1.length + arr2.length;
        int index = length / 2;
        int i = 0;
        int j = 0;
        for (;i + j < index - 1;) {
            if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }
        result = arr1[i] < arr2[j] ? arr1[i] : arr2[j];
        return result;
    }
}

发表于 2023-08-19 18:30:29 回复(0)

Java

触初

import java.util.*;

public class Solution {
/**
* find median in two sorted array
* @param arr1 int整型一维数组 the array1
* @param arr2 int整型一维数组 the array2
* @return int整型
*/
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// write code here
int index = arr1.length;
int index1 = 0;
int index2 = 0;
while (index > index1 + index2) {
if (arr1[index1] < arr2[index2]) {
index1++;
} else {
index2++;
}
}
return Math.max(index1 == 0 ? 0 : arr1[index1 - 1], index2 == 0 ? 0 : arr2[index2 - 1]);
}
}

发表于 2022-05-05 22:50:31 回复(0)

Java

雷欧尼桑

import java.util.*;

// 暴力破解，空间O(1)，时间O(n)
public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int n = arr1.length;
        int l = 0; 
        int r = 0;
        int temp = 0;
        for (int i = 0; i < n; i++) {
            if (arr1[l] < arr2[r]) {
                temp = arr1[l];
                l++;
            } else {
                temp = arr2[r];
                r++;
            }
        }
        return temp;
    }
}

发表于 2022-01-07 23:13:02 回复(0)

Java

老农爱编程

// write code here
        //创建一个数组合并两个数组
        List<Integer> list = new ArrayList<Integer>();
        for(int i : arr1){
            list.add(i);
        }
        for(int i : arr2){
            list.add(i);
        }
        Collections.sort(list);
        //最终中位数肯定是第(arr1.length + arr2.length) / 2 个
        return list.get((arr1.length + arr2.length) / 2 - 1);
    }
我这算不算投机取巧啊 感觉 你们写的都好牛逼

发表于 2022-01-06 22:33:46 回复(0)

Java

YajieC

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int index1 = 0, index2 = 0;
        int count = 0;
        int min = 0;
        while(count < arr1.length){
            if(arr1[index1] < arr2[index2]){
                min = arr1[index1++];
                count++;
            }else{
                min = arr2[index2++];
                count++;
            }
        }
        return min;
    }
}

发表于 2021-12-16 12:05:04 回复(0)

Java

橘子不是唯一的水果yu

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        //采用双指针
        int target = (arr1.length + arr2.length) / 2;
        int left = 0, right = 0;
        int count = 0;
        while(left < arr1.length && right < arr2.length){
            if(arr1[left] <= arr2[right]){
                count++;
                if(count == target) return arr1[left];
                left++;
            }else{
                count++;
                if(count == target) return arr2[right];
                right++;
            }
            
        }
        if(left == arr1.length){
            while(count != target){
                right++;
                count++;
            }
            return arr2[right];
        }
        if(right == arr2.length){
            while(count != target){
                left++;
                count++;
            }
            return arr1[left];
        }
        return -1;
    }
}

发表于 2021-12-15 16:33:32 回复(0)

Java

Carmen-Xiao

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int[] D=merge(arr1,arr1.length,arr2,arr2.length);
        //D的长度一定是偶数 题目给出
        return D[D.length/2-1];//所以这里一定要减去1 可以使用一个测试用例来参考
    }
    public int[] merge(int A[], int m, int B[], int n) {
        int[] help=new int[m+n];
        int p1=0,p2=0,i=0;
        while(p1<m&&p2<n){
            help[i++]=A[p1]<B[p2]?A[p1++]:B[p2++];
        }
        while(p1<m){
            help[i++]=A[p1++];
        }
        while(p2<n){
            help[i++]=B[p2++];
        }
        return help;
    }
}

可以参考合并两个有序数组的代码，得到合并后的数组直接返回对应下标的数组值即可

发表于 2021-12-02 19:30:12 回复(1)

Java

好好刷题进大厂

import java.util.*;

public class Solution {
/**
* find median in two sorted array
* @param arr1 int整型一维数组 the array1
* @param arr2 int整型一维数组 the array2
* @return int整型
*/
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
int right1 = arr1.length-1;
int right2 = arr2.length-1;
int left1 = 0;
int left2 = 0;
int mid1;
int mid2;
int off;
while(left1<right1){
mid1 = (left1+right1)/2;
mid2 = (left2+right2)/2;
off = (right1-left1)%2;
if(arr1[mid1]==arr2[mid2]){
return arr1[mid1];
}
else if(arr1[mid1]<arr2[mid2]){
left1 = mid1+off;
right2= mid2;
}
else{
left2= mid2+off;
right1 = mid1;
}
}
return Math.min(arr1[left1],arr2[left2]);

}

}

发表于 2021-11-23 15:49:41 回复(0)

Java

草莓味的风

方法一：因为是递增数组，所以双指针+遍历数组，找到第n/2个数

时间复杂度 O(n)，空间复杂度 O(1)

public int findMedianinTwoSortedAray2 (int[] arr1, int[] arr2) {
    // write code here
    int len1 = arr1.length,len2 = arr2.length;
    int mid = (len1+len2)/2;
    int index1 = 0,index2=0;
    int count = 0;
    while(count++ < mid-1){
        if(arr1[index1]<arr2[index2]){
            index1++;
        }else{
            index2++;
        }
    }
    return arr1[index1]<arr2[index2]?arr1[index1]:arr2[index2];
}

方法二：二分，时间复杂度为O(logN)，空间复杂度为O(1)

先分别找到两个数组的中位数，比较两个中位数的大小，再根据结果去收缩范围
如果区域数组长度N是奇数（也就是说right1-left1+1是奇数），那个arr1[mid1]和arr2[mid2]的大小有三种情况：
    arr1[mid1]=arr2[mid2]，这个数就是两个数组的上中位数，return arr1[mid1]
    arr1[mid1]>arr2[mid2]，right1=mid1，left2=mid2
    arr1[mid1]<arr2[mid2]，left1=mid1，right2 = mid2
如果区域数组长度N是偶数（也就是说right1-left1+1是偶数），那个arr1[mid1]和arr2[mid2]的大小也有三种情况：
    arr1[mid1]=arr2[mid2]，与上面相同，这个数就是两个数组的上中位数，return arr1[mid1]
    arr1[mid1]>arr2[mid2]，right1=mid1，left2=mid2+1
    arr1[mid1]<arr2[mid2]，left1=mid1+1，right2=mid2
合并上述情况，引入偏移量offset = (right1-left1)%2，则：
    arr1[mid1]=arr2[mid2]，return arr1[mid1]
    arr1[mid1]>arr2[mid2]，right1=mid1，left2=mid2+offset
    arr1[mid1]<arr2[mid2]，left1=mid1+offset，right2=mid2

    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2){
        int left1 = 0,left2 = 0;
        int right1 = arr1.length-1,right2 = arr2.length-1;
        int mid1=0,mid2=0;
        while(left1<right1){
            mid1 = left1 + (right1-left1)/2;
            mid2 = left2 + (right2-left2)/2;
            int offset = (right1 - left1)%2;
            if(arr1[mid1]==arr2[mid2]){
                return arr1[mid1];
            }else if ((arr1[mid1]>arr2[mid2])){
                right1 = mid1 ;
                left2 = mid2 + offset;
            }else{
                left1 = mid1 + offset;
                right2 = mid2 ;
            }
        }
        return arr1[left1]<arr2[left2]?arr1[left1]:arr2[left2];
    }

发表于 2021-10-29 11:02:16 回复(0)

Java

牛客504824151号

public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int c = arr1.length;
        int i = 0;
        int j = 0;
        int index = 0;
        while(c>0) {
            if(arr1[i]<=arr2[j]) {
                index = arr1[i];
                i++;
                c--;
            } else {
                index = arr2[j];
                j++;
                c--;
            }
        }
        return index;
    }

发表于 2021-09-13 10:06:43 回复(0)

Java

谁是谁的眼

public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// write code here

int i = 0,j = 0;
int len1 = arr1.length,len2 = arr2.length;
int cnt = 0,min = 0;
int target = (len1+len2)/2;

while(i < len1 && j < len2){
if(arr1[i] == arr2[j]){
cnt+=2;
i++;
j++;
min = arr1[i-1];
}else if(arr1[i] < arr2[j]){
cnt++;
i++;
min = arr1[i-1];
}else{
cnt++;
j++;
min = arr2[j-1];
}
if(cnt == target){
break;
}
}

return min;
}

发表于 2021-08-22 21:14:23 回复(0)

Java

又笨又懒不想上课

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int n = arr1.length;
        int l = 0, r = 0,res = 0;
        while(l + r < n) {
            if(arr1[l] < arr2[r]) res = arr1[l++];
            else res = arr2[r++];
        }
        return res;
    }
}

发表于 2021-06-13 18:41:57 回复(1)

Java

牛客597539055号

    public int findMedianinTwoSortedAray (int[] nums1, int[] nums2) {
        if(nums1 == null && nums2 == null) return 0;
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return Math.min(findKth(nums1, 0, nums2, 0, left), findKth(nums1, 0, nums2, 0, right));
    }
    
        //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }

发表于 2020-11-22 18:36:29 回复(0)

提交观点

问题信息

数组二分分治

难度：

24条回答 511收藏 4553浏览

通过挑战的用户

查看代码

牛客30382...

2022-12-23 10:51:46
你今天学到了啥

2022-11-27 17:06:58
牛客58370...

2022-09-28 02:02:49
那就开摆

2022-09-18 22:26:14
Domingoz

2022-09-16 16:22:54

在两个长度相等的排序数组中找到上中位数

输入

输出

说明

输入

输出

说明

输入

输出

备注:

方法一：因为是递增数组，所以双指针+遍历数组，找到第n/2个数

方法二：二分，时间复杂度为O(logN)，空间复杂度为O(1)

问题信息

热门推荐

通过挑战的用户

相关试题