[NC]36. 在两长度相等的有序数组中找中位数

🚩传送门：牛客题目

题目

给定两个递增数组 和 ，已知两个数组的长度都为 ，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为 ，为第 个数

解题思路：双指针

假设将两个数组合并为一个数组，先算出上中位数在合并后的数组中的下标位置 。然后模拟二路归并，当下标到达上中位数时返回结果。

题目加速过程：

1. 合并后数组的上中位数下标数值 ，可以理解为：**i** , **j**需要移动的次数 。
2. 当有一方指针越界，另外一方可以直接求出 。

   举例子：现在假设 mid = 1

   1. 我们可以知道 上中位数 在合并后数组中的下标为 1
   2. ，需要移动的次数 为 1

   ，初始一定指向(且其中有一个在合并后数组中的位置为 )，因此，中有一个指针只需要走 **1** 步就可以到达上中位数的位置。

   那么当其中一个指针失效时可以直接计算答案，因为还剩下 步没走，不妨设为越界，那么直接走完剩余路程就可以到达上中位数

复杂度分析

时间复杂度：，其中 为合并后数组的长度。

空间复杂度：，使用常数的空间

我的代码

public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        //0. 获取数组长度
        int a1len = arr1.length;
        int a2len = arr2.length;
        //1. 计算合并后数组中的上中位数位置(或者说i,j需要移动的次数)
        int mid = a1len + (a2len - a1len + 1) / 2-1;
        int j = 0, i = 0;
        //2. 假装二路归并
        while (i < a1len && j < a2len) {
            if (mid-- == 0)
                return Math.min(arr1[i], arr2[j]);
            if (arr1[i] < arr2[j])
                i++;
            else
                j++;
        }
        // 当arr2走完的时候，arr1还没走完，此时上中位数则在arr1中
        if (i < a1len)
            return arr1[i + mid];// i 将剩余的 mid 步走完
        else
            return arr2[j + mid];// j 将剩余的 mid 步走完
    }
}

解题思路：二分查找

时间复杂度度要求为，很容易就想到了二分查找。

算法是思路为：

先定位到两个数组的中位数，比较此时两个中位数对应的数的大小，再根据结果去进行调整，以数组1不超出范围为循环条件，每次比较区间范围的中位数的大小，将left1和left2这两个指针始终指向可能的中位数的位置，因为数组是从小到大进行排序的。

复杂度分析

时间复杂度：，其中 为合并后数组的长度。

空间复杂度：，使用常数的空间

我的代码

import java.util.*;
public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        if(arr1 == null || arr2 == null || arr1.length!=arr2.length){
            return 0;
        }
        // 数组1的左边界
        int left1 = 0;
        // 数组1的右边界
        int right1 = arr1.length - 1;
        // 数组2的左边界
        int left2 = 0;
        // 数组2的右边界
        int right2 = arr2.length - 1;
        // 数组1的中点
        int mid1 = 0;
        // 数组2的中点
        int mid2 = 0;
        // 偏移量
        int offset = 0;
        while(left1 < right1){
            // 找到两个数组的中点
            mid1 = left1+(right1 - left1) / 2;
            mid2 = left2+(right2 - left2) / 2;
            offset = ((right1 - left1 + 1)&1)^1;  //位运算比对2取余要快
            // 当此时arr1中点位置大于arr2中点位置时
            if(arr1[mid1] > arr2[mid2]){
                // 调整arr1的右边界为mid1
                right1 = mid1;
                // 数组2的左边界调整为当前位置+偏移量
                left2 = mid2 + offset;
            }else if(arr1[mid1] < arr2[mid2]){
                right2 = mid2;
                left1 = mid1 + offset;
            }else {
                // 当相等的时候，则中位数即为此时
                return arr1[mid1];
            }
        }
        // 中位数为数组1的左指针的位置，或者数组2的左指针的位置
        return Math.min(arr1[left1],arr2[left2]);
    }
}