首页 > 试题广场 >

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

[编程题]在两个长度相等的排序数组中找到上中位数
  • 热度指数：36101 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，为第n/2个数

数据范围：，

要求：时间复杂度 ，空间复杂度
进阶：时间复杂度为，空间复杂度为

示例1

输入

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

输出

3

说明

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

输入

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

输出

2

说明

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

输入

[1],[2]

输出

1

备注:

算法知识视频讲解
添加回答
Java
许愿简历通过的干饭人很快乐头像 许愿简历通过的干饭人很快乐
直接计算出中上位所在位置，开始比较大小，到那一位直接输出； 
import java.util.*;


public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        
        int num = (arr1.length+arr2.length)/2;


        int i=0,j=0,k=0,nums=0;

        while(i!=num){
            nums = arr1[j]<arr2[k]?arr1[j++]:arr2[k++];
            i++;
        }
        
        return nums;
    }
}


发表于 2024-08-09 18:28:27 回复(0)
Java
牛客148901号头像 牛客148901号 
import java.util.*;


public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        int i = 0;
        int j = 0;
        int mid = -1;
        int index = 0;
        int count = (m + n) / 2;
        while (i < m && j < n) {
            if (arr1[i] <= arr2[j]) {
                mid = arr1[i++];
            } else {
                mid = arr2[j++];
            }
            index++;
            if (index == count) {
                return mid;
            }
        }
        while (i < m) {
            mid = arr1[i++];
            index++;
            if (index == count) {
                return mid;
            }
        }
        while (j < n) {
            mid = arr2[j++];
            index++;
            if (index == count) {
                return mid;
            }
        }
        return mid;
    }
}

发表于 2024-05-12 10:18:41 回复(0)
Java
牛客294317031号头像 牛客294317031号 
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号头像 牛客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头像 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头像 橘子不是唯一的水果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头像 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号头像 牛客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)
提交观点

问题信息

数组 二分 分治
难度：
28条回答 7134浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号