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

牛客205301162号

举个例子：

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)

一棵树_

  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)

牛客112358830号

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)

C/C++

breeze_blows

参考解法https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

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)

C/C++

卷卷更健康

都说这道题是披着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)

portal20

写了个针对一般情况的。另外，如果总数是偶数，那么应该是第 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)

ruiruisun

我信你个鬼，你个题解超时坏的狠😣（python）

发表于 2020-11-17 11:46:00 回复(0)

zbp同学

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)

C/C++

流浪剑士

感觉题目埋了坑，只说有序数组，但没说升序降序，也没说两个数组排序是否相同，另外题目中上中位数定义感觉有问题

题目中的定义：假设递增序列长度为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)

moocleanrn

这道题很难啊

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)，很容易想到二分查找。过程如下：

如果每个数组中只有一个元素，较小的那个元素就是整体的上中位数，如果两个元素相等，随便返回哪个都可以。
如果数组中不止一个元素，找到两个数组的中间位置mid1和mid2。
如果arr1[mid1] == arr2[mid2]，不管每个数组中元素的个数是奇数还是偶数，这两个数都可以是整体的上中位数，返回其中一个就可以。
如果arr1[mid1] > arr2[mid2]，每个数组的个数是奇数的情况下：数组arr1中mid1位置以后的数都不可能是整体的上中位数，数组arr2中mid2位置以前的数都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2…right]，这两部分的元素个数相同，它们的上中位数就是整体的上中位数。
如果arr1[mid1] > arr2[mid2]，每个数组的个数是偶数的情况下：数组arr1中mid1位置以后的数都不可能是整体的上中位数，数组arr2中mid2位置以后包括mid2位置，都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2+1…right]，这两部分的元素个数相同，它们的上中位数就是整体的上中位数。
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)

C/C++

酣饮幻恒

思路一：思路就是从两个数组不断找较小者，找到第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)

Python3

大胆的退堂鼓鼓手在冲浪

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)

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)

C/C++

无敌的神龙战士

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)

Java

牛客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)

牛客910752787号

    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)

万顺佑

<pre class="prettyprint lang-java">//双指针白 public int findMedianinTwoSortedAray(int[] arr1, int[] arr2) { int n = (arr1.length + arr2.length + 1) / 2; int p1 = 0; int p2 = 0; int ans = 0; for (int i = 0; i < n; i++) { if (arr1[p1] <= arr2[p2]) ans = arr1[p1++]; else ans = arr2[p2++]; } return ans; }</pre> <br>

编辑于 2023-05-12 15:58:23 回复(1)

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

输入

输出

说明

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题