题意分析

  • 给你两个数组。
    • 数组都是按照从小到达进行排序的
    • 两个数组的大小相等
  • 需要我们求出两个数组的上中位数
    • 上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数
    • 同时时间复杂度为O(logn)，空间复杂度为O(1)

思路分析

  • 其实稍微了解过排序算法的同学都应该知道，这个其实和排序算法里面的归并排序里面的归并的思想和类似。归并，也叫做分治思想。我们需要对数组进行排序的时候，我们先进行划分区间，将数组划分为一块一块小的区间的时候，我们就将这个数组两两进行归并，进而实现大的数组的有序。而这个题目就提供了两个有序的数组，需要合并成一个，这其实和归并的思想不谋而合了。

解法一 双指针枚举

  • 我们发现，其实我们完全就可以使用两个指针跑一遍完事的。我们用两个指针，一个指向数组1，一个指向数组2，然后，比较两个之间大小，元素更小的指针进行向后移动，我们可以发现，最后在循环里面一定可以找到最终的答案，因为我们只需要找到n个数字即可。

图片说明

  • 如上图

  • 代码如下

    • 需要遍历到n个数字，时间复杂度为O(n)，这个时间复杂度显然不符合题目要求。
    • 只开了几个变量进行处理，空间复杂度为O(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 l=0,r=0;
        int n=arr1.size();
        int sum=0; // sum记录此时找到了多少个数字
        while(l<n&&r<n){
            // 如果数组1此时指向的数字小于数组2的，那么数组1移动
            if(arr1[l]<arr2[r]){
                sum++;
                // 如果刚好到了n，那么直接返回
                if(sum==n){
                    return arr1[l];
                }
                // 数组1指针移动
                l++;
            }else{
                // 如果数组2此时指向的数字小于数组1的，那么数组2移动
                sum++;
                if(sum==n){
                    // 如果刚好到了n，那么直接返回
                    return arr2[r];
                }
                // 数组2指针移动
                r++;
            }
        }
        // 其实这个随便返回都可，因为肯定会在while里面返回，这个是为了防止语法错误
        return arr1[n-1];
    }
};

解法二 二分法

  • 二分法是在上面的这种解法里面进行优化的，我们发现，最后我们找到的数字具有单调性。我们分别对这两个数组进行二分操作，如果数组1的mid位置的数字小于数组2的mid，那么我们把数组1的左指针移动到中间，数组2的右指针移到中间。但是这里要注意，假如这个区间的长度是奇数，那么就是区间中点+1，否则就是区间中点；数组2的情况也是一样。如果此时两者的mid一样，那么合并之后这个数字的左右两边的个数一定是相等的。这个就是上中位数。否则，最后只需要返回两个数组的左指针指向的最小的那个数字就行了。因为上中位数一定小于等于下中位数。

  • 代码如下

    • 使用二分进行求解，显然时间复杂度为O(logn)，符合题目要求
    • 只使用了几个变量进行求解，空间复杂度为O(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 l1=0,r1=n-1; // 定义数组1的左右指针
        int l2=0,r2=n-1; // 定义数组2的左右指针
        while(l1<r1){  // 始终保持数组1的左指针小于右指针
            int even=(r1-l1)%2;  // 数组的长度
            int mid1=(l1+r1)>>1; // 数组1的中点
            int mid2=(l2+r2)>>1;  // 数组2的中点
            if(arr1[mid1]>arr2[mid2]){  
                // 如果数组1的中点大于数组2的中点,数组2的左指针右边移动，数组1的右指针左边移动
                l2=mid2+even;
                r1=mid1;
            }else if(arr1[mid1]<arr2[mid2]){
                l1=mid1+even;
                r2=mid2;
            }else{
                // 如果区间中点一样，一定是上中位数
                return arr1[mid1];
            }
        }

        // 返回更小的那个，因为上中位数比下中位数小
        return min(arr1[l1],arr2[l2]);
    }
};