首页 > 试题广场 >

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

[编程题]在两个长度相等的排序数组中找到上中位数
  • 热度指数:32969 时间限制: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

备注:

举个例子:
 arr1:1,2,8,9
 arr2:3,4,5,6
 这里两个数组的长度均为4,
第一步:(3+0)/2=1,所以比较2和4,
1,   2,   8,9
3,   4,   5,6
由于2<4,所以结果一定在如下两个子集,那么下一步判断这两个子集,
1,2,  8,9
3,4,  5,6
对于arr1,(3+2)/2=2,对于arr2,(0+1)/2=0,所以判断8和3
1,2,   8,   9
3,   4,   5,6
由于3小于8,所以仍需判断:
1,2,   8,   9
3,   4,   5,6
此时只需返回较小值4即可。

判断条件为两个元素相等或只剩下一个元素。

代码如下:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        if(arr1.size()==0 || arr2.size()==0)
            return -1;
        return recurseFindMedian(arr1, arr2, 0, arr1.size()-1, 0, arr2.size()-1);
    }
    
    int recurseFindMedian(vector<int>& arr1, vector<int>& arr2, int s1, int e1, int s2, int e2) {
        
        if(s1==e1 && s2==e2)
            return min(arr1[s1], arr2[s2]);

        int mid1 = (e1+s1)/2;
        int mid2 = (e2+s2)/2;
        if(arr1[mid1] == arr2[mid2])
            return arr1[mid1];
        return arr1[mid1] < arr2[mid2] ? 
            recurseFindMedian(arr1, arr2, e1-mid2+s2, e1, s2, mid2) :
            recurseFindMedian(arr1, arr2, s1, mid1, e2-mid1+s1, e2);
    }

编辑于 2021-04-09 12:56:06 回复(1)
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int l1 = 0, r1 = arr1.size() - 1, l2 = 0, r2 = arr2.size() - 1;
        
        while(l1 < r1){
            int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
            //判断子区间的个数是奇数还是偶数 0代表是奇数(奇数中间的数字不能删除) 1代表是偶数
            int even = (r1 - l1) % 2;
            if(arr1[mid1] == arr2[mid2]){
                return arr1[mid1];
            } else if (arr1[mid1] > arr2[mid2]){
                //证明arr1前面的子数组没用 arr2后面的子数组没用
//                 r1 = mid1 + even; //如果是奇数就是啥都不做 
                /*
                3456 1234 得取34所有 l2 应该向后面取一位
                */
                r1 = mid1;
                l2 = mid2 + even;
            } else {
                l1 = mid1 + even; //如果是偶数 就是它的后一位
                r2 = mid2; 
            }
        }
        //如果俩个数组剩下最后一个数 且不相等 返回其中较小的那个即可
        return min(arr1[l1],arr2[l2]);
    }
};

发表于 2021-04-01 17:00:32 回复(1)
  public static int findMedianinTwoSortedAray(int[] nums1, int[] nums2) {
        /**
         * 设nums1长度为m,nums2长度为n,设m <= n
         * 将nums1与nums2分别进行分组,设nums1的左边长度为i,则右边长度 m - i;设nums2的左边长度为j,则右边长度为 n - j
         * 如果m + n 为偶数,则有 i + j = m - i + n - j,如果 m + n 是奇数,则有 i + j = m - i + n - j + 1
         * 因此有 j = (m + n + 1)/2 - i,(因为只取商,所以 m + n 的和无论是偶数还是奇数都满足这个结果)
         * 还有 nums1[i - 1] <= nums2[j] 且 nums1[i] >= nums2[j - 1]
         *
         * 又因为 i ∈ [0, m],如果需要同时满足条件( nums1[i - 1] <= nums2[j] 且 nums1[i] >= nums2[j - 1])
         * 所以可以取最大的 i 使其满足nums1[i - 1] <= nums2[j]即可
         *
         */
        if (nums1.length > nums2.length) {
            return findMedianinTwoSortedAray(nums2, nums1);
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int start = 0;
        int end = len1;
        int median1 = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            int nums2Index = (len1 + len2 + 1) / 2 - mid;
            int nums1Left = mid == 0 ? Integer.MIN_VALUE : nums1[mid - 1];
            int nums1Right = mid == len1 ? Integer.MAX_VALUE : nums1[mid];
            int nums2Left = nums2Index == 0 ? Integer.MIN_VALUE : nums2[nums2Index - 1];
            int nums2Right = nums2Index == len2 ? Integer.MAX_VALUE : nums2[nums2Index];
            if (nums1Left <= nums2Right) {
                median1 = Math.max(nums1Left, nums2Left);
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return median1;
    }


发表于 2021-01-07 17:00:38 回复(1)
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        int n = arr1.size();
        int left = 0, right = n-1;  // binary search [0,n-1)
        while(left < right) {
            int m1 = left + ((right - left) >> 1);  // 
            int m2 = n - m1 - 2;
            if(arr1[m1] > arr2[m2+1]) {
                right = m1;
            }else if(arr2[m2] > arr1[m1+1]) {
                left = m1 + 1;
            }else if(arr1[m1] <= arr2[m2+1] && arr2[m2] <= arr1[m1+1]) {
                return max(arr1[m1], arr2[m2]);
            }
        }
        if(left == n-1) return arr1[n-1];
        if(right == 0)  return arr2[n-1];
    }
};
两个指针i, j 指向数组1第i个,数组2第j个。 
i + j == n;
从第1个数组,[0, n-1)二分,若满足a[i]<= b[j+1] && b[j] <= a[i+1] 则ans = max(a[i], b[j]);
发表于 2020-10-23 03:45:22 回复(1)
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int m = arr1.size();
        return getKmin(arr1, 0, m-1, arr2, 0, m-1, m);
        
    }
    
    int getKmin(vector<int>& nums1, int l1, int r1, vector<int>& nums2, int l2, int r2, int k){
        int len1 = r1-l1+1;
        int len2 = r2-l2+1;
        if(len1 == 0){
            return nums2[l2+k-1];
        }
        if(len2 == 0){
            return nums1[l1+k-1];
        }
        if(k == 1){
            return min(nums1[l1], nums2[l2]);
        }

        int nl1 = l1 + min(len1, k/2) - 1;
        int nl2 = l2 + min(len2, k/2) - 1;
        if(nums1[nl1] <= nums2[nl2]){
            return getKmin(nums1, nl1+1, r1, nums2, l2, r2, k - (nl1-l1+1));
        }
        else{
            return getKmin(nums1, l1, r1, nums2, nl2+1, r2, k - (nl2-l2+1));
        }
    }
};












发表于 2021-05-22 21:27:45 回复(0)
都说这道题是披着medium皮的hard,我稀里糊涂的过了,也不知道对不对,这里说下大概思路:2个排序数组取第n大的数
1. 数组1取 m1 个,数组2 取 m2 个数,则有 m1+m2 = n
2. m1 和 m2 通过二分求取。
满足答案的条件有三种情况(前提是 m1+m2 == n):
1. arr1[m1] == arr2[m2] -> arr1[m1];
2. (arr1[m1] < arr2[m2]) && (m2 == 0 || (m2 > 0 && arr1[m1] >= arr2[m2-1])) -> arr1[m1];
3. (arr2[m2] < arr1[m1]) && (m1 == 0 || (m1 > 0 && arr2[m2] >= arr1[m1-1]))-> arr2[m2];
其他情况,则调整 m1,m2 的指,完整代码如下:
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
    // write code here
    int n = arr1.size() - 1;
    int l1 = 0,h1 = n,l2 = 0,h2 = n,m1,m2;
    while(l1 <= h1 && l2 <= h2) {
        m1 = (l1 + h1)/2;
        m2 = (l2 + h2)/2;
        if (m1 + m2 == n) {
            if (arr1[m1] == arr2[m2]) return arr1[m1];
            else if (arr1[m1] < arr2[m2]) {
                if (m2 == 0 || (m2 > 0 && arr1[m1] >= arr2[m2-1])) return arr1[m1];
                else l1 = m1 + 1;
            }
            else {
                if (m1 == 0 || (m1 > 0 && arr2[m2] >= arr1[m1-1])) return arr2[m2];
                else l2 = m2 + 1;
            }
        }
        else if (m1 + m2 < n) {
            if (arr1[m1] < arr2[m2]) l1 = m1 + 1;
            else l2 = m2 + 1;
        }
        else {
            if (arr1[m1] > arr2[m2]) h1 = m1 - 1;
            else h2 = m2 - 1;
        }
    }
    return 0;
}


编辑于 2021-04-02 11:51:19 回复(1)
写了个针对一般情况的。另外,如果总数是偶数,那么应该是第 N / 2 个和第 N / 2 + 1 个求平均(N为总长)。这里比较特殊,就按题目的要求来。

当然,最简单的就是合并两个有序数组然后找第 xx 个。时间复杂度为O(n)。
import java.util.*;

public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int m = arr1.length, n = arr2.length;
        
        if ((m + n) % 2 == 1) {
            return findK(arr1, arr2, 0, m - 1, 0, n - 1, (m + n) / 2 + 1);
        }
        else {
            return findK(arr1, arr2, 0, m - 1, 0, n - 1, (m + n) / 2);
        }
    }
    
    //在两个有序数组中找第 K 个
    private int findK(int[] a1, int[] a2, int l1, int r1, int l2, int r2, int k) {
        //其中一方越界
        if (l1 > r1)
            return a2[l2 + k - 1];
        if (l2 > r2)
            return a1[l1 + k - 1];
        
        //注意基本情况 k == 1
        if (k == 1)
            return Math.min(a1[l1], a2[l2]);
        
        int ind1, len1, ind2, len2;
        //优先考虑长度比较短的一方,正常来说应该要取 k / 2 个数,但是要考虑长度不够的情况
        //另一方取的就是 k - 已经取了的
        if (r1 - l1 <= r2 - l2) {
            len1 = Math.min(k / 2, r1 - l1 + 1);
            len2 = k - len1;
        }
        else {
            len2 = Math.min(k / 2, r2 - l2 + 1);
            len1 = k - len2;
        }
        ind1 = l1 + len1 - 1;
        ind2 = l2 + len2 - 1;
        
        //更新范围。小的一方后半段 + 大的一方前半段。
        //更新k。小的一方前半段肯定在前 k 个的范围,减掉找剩下的
        if (a1[ind1] <= a2[ind2]) {
            return findK(a1, a2, ind1 + 1, r1, l2, ind2, k - len1);
        }
        else {
            return findK(a1, a2, l1, r1, ind2 + 1, r2, k - len2);
        }
        
    }
}

 
编辑于 2021-03-25 14:24:18 回复(1)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
    // write code here
    int p1=0,p2=0,mid=0;

    for(int i=0;i<arr1.length;i++){
        if(arr1[p1]<=arr2[p2]){
            mid=arr1[p1];
            p1++;
        }else{
            mid=arr2[p2];
            p2++;
        }
    }

    return mid;
}

发表于 2020-11-20 20:47:00 回复(0)
我信你个鬼,你个题解超时坏的狠😣(python)
发表于 2020-11-17 11:46:00 回复(0)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
    //和leetcode的 两个有序数组的中位数 很像。
    int l=0,r=arr1.length,mid=0;
    int n=arr1.length;
    if (n==0)
        return 0;
    int j=0;
    while (l<=r){
        mid=(l+r)/2;//往arr1中取出mid个数
        j=n-mid;//往arr2中取出多少个数

        int arr1_left=mid==0?Integer.MIN_VALUE:arr1[mid-1];
        int arr1_right=mid==n?Integer.MAX_VALUE:arr1[mid];
        int arr2_left=j==0?Integer.MIN_VALUE:arr2[j-1];
        int arr2_right=j==n?Integer.MAX_VALUE:arr2[j];

        int left_max=Math.max(arr1_left,arr2_left);
        int right_min=Math.min(arr1_right,arr2_right);

        if (left_max<right_min)
            return left_max;
        else if (arr1_left<arr2_left){
            l=mid+1;
        }else
            r=mid;
    }
    return 0;
}
编辑于 2020-10-04 17:23:30 回复(0)
class Solution {
public:
    vector<int> arr1; vector<int> arr2;
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int n1 = arr1.size(); int n2 = arr2.size();
        this->arr1.swap(arr1); this->arr2.swap(arr2);
        return findKthMin(0, n1, 0, n2, (n1 + n2 + 1) / 2);
    }

    int findKthMin(int b1, int e1, int b2, int e2, int k) {
        if(b1 == e1) return arr2[b2 + k - 1];
        if(b2 == e2) return arr1[b1 + k - 1];
        if(k == 1) return min(arr1[b1], arr2[b2]);
        int m = min({k / 2, e1 - b1, e2 - b2});
        if(arr1[b1 + m - 1] < arr2[b2 + m - 1])
            return findKthMin(b1 + m, e1, b2, e2, k - m);
        else
            return findKthMin(b1, e1, b2 + m, e2, k - m);
    }
};
发表于 2020-09-02 17:22:21 回复(0)
感觉题目埋了坑,只说有序数组,但没说升序降序,也没说两个数组排序是否相同,另外题目中上中位数定义感觉有问题
题目中的定义:假设递增序列长度为n,若n为奇数,则上中位数为第n/2+1个数;否则为第n个数
两个长度都为N的数组,合并后长度为2N,肯定为偶数,只需要输出两个数组中最大的数就行了,但和下面给的例子不符,偶数时上中位数应为第n/2个数
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        //题目出的有漏洞,两个长度都为N的数组,合并后长度为2N,肯定为偶数
        //按照题目中上中位数定义:假设递增序列长度为n,若n为奇数,则上中位数为第n/2+1个数;否则为第n个数 
        //只需要输出两个数组中最大的数就行了,偶数时上中位数应为第n/2个数
        if(arr1.size()==0 && arr2.size() == 0)
        {
            return 0;
        }
        //如果有一个是空数组,返回另外一个数组的上中位数
        if(arr1.size() == 0)
        {
            return midvalue(arr2);
        }
        if(arr2.size() == 0)
        {
            return midvalue(arr1);
        }
        int len = arr1.size()+arr2.size();
        //计算上中位数坐标
        int midindex = len/2;
        if(len%2 == 0)
        {
            midindex -= 1;
        }
        
        int index1 = 0;
        int step1 = 1;
        int limit1 = arr1.size();
        int min1 = arr1[0];
        int max1 = arr1[arr1.size()-1];
        int index2 = 0;
        int step2 = 1;
        int limit2 = arr2.size();
        int min2 = arr2[0];
        int max2 = arr2[arr2.size()-1];
        if(min1 > max1)//数组1为降序,从尾部开始遍历
        {
            index1 = arr1.size()-1;
            step1 = -1;
            limit1 = 0;
            min1 = arr1[arr1.size()-1];
            max1 = arr1[0];
        }
        if(min2 > max2)//数组2为降序,从尾部开始遍历
        {
            index2 = arr2.size()-1;
            step2 = -1;
            limit2 = 0;
            min2 = arr2[arr2.size()-1];
            max2 = arr2[0];
        }
        //优化增加边界判断,如果一个数组的最小值大于等于另外一个数组的最大值,可以直接通过坐标值取得结果
        if(min2 >= max1)
        {
            if(midindex < arr1.size())
            {
                if(step1 == 1)
                {
                    return arr1[midindex];
                }
                else
                {
                    return arr1[arr1.size() - 1 - midindex];
                }
            }
            else
            {
                if(step2 == 1)
                {
                    return arr2[midindex - arr1.size()];
                }
                else
                {
                    return arr2[arr2.size() - 1 - midindex + arr1.size()];
                }
            }
        }
        if(min1 >= max2)
        {
            if(midindex < arr2.size())
            {
                if(step2 == 1)
                {
                    return arr2[midindex];
                }
                else
                {
                    return arr2[arr2.size() - 1 - midindex];
                }
            }
            else
            {
                if(step1 == 1)
                {
                    return arr1[midindex - arr2.size()];
                }
                else
                {
                    return arr1[arr1.size() - 1 - midindex + arr2.size()];
                }
            }
        }
        
        for(int i=0;i<=midindex;i++)
        {
            if(i == midindex)
            {
                if(index1 != limit1 && index2 != limit2)
                {
                    if(arr1[index1] < arr2[index2])
                    {
                        return arr1[index1];
                    }
                    else
                    {
                        return arr2[index2];
                    }
                }
                else if(index1 != limit1)
                {
                    return arr1[index1];
                }
                else if(index2 != limit2)
                {
                    return arr2[index2];
                }
            }
            else
            {
                if(index1 != limit1 && index2 != limit2)
                {
                    if(arr1[index1] < arr2[index2])
                    {
                        index1 += step1;
                    }
                    else
                    {
                        index2 += step2;
                    }
                }
                else if(index1 != limit1)
                {
                    index1 += step1;
                }
                else if(index2 != limit2)
                {
                    index1 += step1;
                }
            }
        }
        return 0;
    }
    
    int midvalue(vector<int>& arr)
    {
        int size = arr.size();
        if(size%2 == 0)
        {
            if(arr[0] < arr[size-1])
            {
                return arr[size/2 - 1];
            }
            else
            {
                return arr[size/2];
            }
        }
        else
        {
            return arr[size/2];
        }
    }
};


发表于 2020-08-28 14:57:40 回复(4)
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)
这道题很难啊
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int auxi(vector<int>& arr1, int p1, int p2, vector<int>& arr2, int q1, int q2) {
        if (p1  == p2 - 1) {
            return min(arr1[p1], arr2[q1]);
        }
        int mid1 = (p1 + p2) / 2;
        int mid2 = (q1 + q2) / 2;
        if ((p2 - p1) % 2 == 0) { // 偶数
            if (arr1[mid1-1] == arr2[mid2-1]) return arr1[mid1-1];
            else if (arr1[mid1-1] > arr2[mid2-1]) {
                return auxi(arr1, p1, mid1, arr2, mid2, q2);
            } else {
                return auxi(arr1, mid1, p2, arr2, q1, mid2);
            }
        } else { // 奇数
            if (arr1[mid1] == arr2[mid2]) return arr1[mid1];
            else if (arr1[mid1] > arr2[mid2]) {
                return auxi(arr1, p1, mid1+1, arr2, mid2, q2);
            } else {
                return auxi(arr1, mid1, p2, arr2, q1, mid2 + 1);
            }
        }
    }
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        return auxi(arr1, 0, arr1.size(), arr2, 0, arr2.size());
    }
};
发表于 2021-03-20 15:53:45 回复(2)

看到时间复杂度为O(logN),很容易想到二分查找。过程如下:

  1. 如果每个数组中只有一个元素,较小的那个元素就是整体的上中位数,如果两个元素相等,随便返回哪个都可以。

  2. 如果数组中不止一个元素,找到两个数组的中间位置mid1和mid2。

  3. 如果arr1[mid1] == arr2[mid2],不管每个数组中元素的个数是奇数还是偶数,这两个数都可以是整体的上中位数,返回其中一个就可以。

  4. 如果arr1[mid1] > arr2[mid2],每个数组的个数是奇数的情况下:数组arr1中mid1位置以后的数都不可能是整体的上中位数,数组arr2中mid2位置以前的数都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2…right],这两部分的元素个数相同,它们的上中位数就是整体的上中位数。

  5. 如果arr1[mid1] > arr2[mid2],每个数组的个数是偶数的情况下:数组arr1中mid1位置以后的数都不可能是整体的上中位数,数组arr2中mid2位置以后包括mid2位置,都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2+1…right],这两部分的元素个数相同,它们的上中位数就是整体的上中位数。

  6. arr1[mid1] < arr2[mid2]的情况,分析同上。

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    //由时间复杂度,想到二分查找
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        int n = arr1.size();
        if(n==0){
            return NULL;
        }
        //arr1左右两端
        int l1=0,r1=n-1;
        //arr2左右两端
        int l2=0,r2=n-1;
        int mid1,mid2;
        //终止条件为l1=r1,即两个数组都只有一个元素,此时的上中位数为两数的最小值
        while(l1< r1){ 
            //arr1中位数
            mid1 = l1+((r1-l1)>>1);
            //arr2中位数
            mid2 = l2+((r2-l2)>>1);
            int k = r1-l1+1;
            if(arr1[mid1] == arr2[mid2]){ //若两数组中位数相等,整体中位数也是这个
                return arr1[mid1];
            }
            else if(arr1[mid1] > arr2[mid2]){
                if(k%2 == 0){//区间元素个数为偶数
                    r1 = mid1; //整体中位数在arr1左区间,包括mid1
                    l2 = mid2+1; //整体中位数在arr2右区间,不包括mid2
                }
                else if(k%2 == 1){ //区间元素个数为奇数
                    r1 = mid1; //整体中位数在arr1左区间,包括mid1
                    l2 = mid2; //整体中位数在arr2右区间,包括mid2
                }
            }
            else if (arr1[mid1] < arr2[mid2]){
                if(k%2 == 0){//区间元素个数为偶数
                    r2 = mid2; //整体中位数在arr2左区间,包括mid2
                    l1 = mid1+1; //整体中位数在arr1右区间,不包括mid1
                }
                else if(k%2 == 1){ //区间元素个数为奇数
                    r2 = mid2; //整体中位数在arr2左区间,包括mid2
                    l1 = mid1; //整体中位数在arr1右区间,包括mid1
                }
            }
        }
        //当区间内只有一个元素时,两个区间中最小值即为整体中位数
        return min(arr1[l1],arr2[l2]);
    }
};

发表于 2020-09-01 11:34:17 回复(6)
思路一:思路就是从两个数组不断找较小者,找到第n个就返回。
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        int l = 0, r = 0;
        int res = 0;
        while(l + r < arr1.size()){
            if(arr2[r] < arr1[l])
                res = arr2[r++];
            else
                res = arr1[l++];
        }
        return res;
    }
};
思路二:二分arr1,可以得到对应的arr2(保证arr1的前i个和arr2的前j个刚好凑够N个)
class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        int N = arr1.size();
        int l = 0, r = N-1;
        int res = 0;
        while(l <= r){
            int mid = (l+r)>>1;
            if(mid == N-1)
                return min(arr1[N-1], arr2[0]);
            if(arr1[mid] == arr2[N-mid-2])
                return arr1[mid];
            if(arr1[mid] < arr2[N-mid-2]){
                l = mid+1;
            }
            else
                r = mid-1;
        }
        if(r < 0)
            return min(arr1[0], arr2[N-1]);
        int a = max(arr1[l], arr2[N-2-l]);
        int b = max(arr1[r], arr2[N-2-r]);
        return min(a, b);
    }
};


编辑于 2020-08-31 20:38:30 回复(1)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int len = arr1.length;
        int a1 = 0;
        int a2 = 0;
        while(len>1){
            if(arr1[a1]<=arr2[a2])a1++;
            else a2++;
            len--;
        }
        return Math.min(arr1[a1],arr2[a2]);
    }
不需要想的太复杂,既然题目说了是有序数组,那就双指针分别指向两个数组,按大小顺序
移动,移动次数为数组长度(题目中说的偶数奇数情况根本没用,因为两个数组长度相等,
不可能得到奇数个数字,中位数必然是第arr1.length个),指针移完了就取两个数组中小的。

发表于 2020-09-03 16:47:58 回复(5)
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)
class Solution:
    def findMedianinTwoSortedAray(self , arr1: List[int], arr2: List[int]) -> int:
        for i in arr2:
            arr1.append(i)
        arr1.sort()
        n=int(len(arr1)/2)
        return(arr1[n-1])
发表于 2023-03-16 14:55:51 回复(0)
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        //上中位数的下标
        int k = arr1.length - 1;
        int i = 0, j = 0, s = 0;
        //遍历两个数组,比较两个数组元素大小,直到遍历次数=上中位数的下标
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                if (s == k) {
                    return arr1[i];
                }
                i++;
            } else {
                if (s == k) {
                    return arr2[j];
                }
                j++;
            }
            s++;
        }
        return 0;
    }


发表于 2022-09-20 20:28:04 回复(0)