力扣——4. 寻找两个正序数组的中位数

题目：

思路：

1.先将两个数组进行合并，分别计算数组1和数组2的长度l=m+n;

2.定义两个指针，分别放在两个数组的最后一个位置 ；

3.判断，因为是正序（从小到大）的数组，所以可以判断nums1第一个数是否大于nums2第一个数nums1[aStart]<nums2[bStart]

4.判断，是否还有余下的数，如果有，直接放到后面

代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        // 合成的数组
        int[] res = new int[len1+len2];
        int index = 0;
        int left = 0, right = 0;
        // 归并排序合成部分
        while(left<len1&&right<len2) {
            if(nums1[left]<nums2[right]) {
                res[index++] = nums1[left++];
            } else {
                res[index++] = nums2[right++];
            }
        }
        // 判断nums1剩余还是nums2剩余，并将剩余部分加入到合成的数组之后
        while(left<len1) {
            res[index++] = nums1[left++];
        }
        while(right<len2) {
            res[index++] = nums2[right++];
        }
        // 判断合成后的数组的长度，求出中位数。返回的是double类型
        if((len1+len2)%2==1) {
            return (double) res[(len1+len2)/2];
        } else {
            return (double) (res[(len1+len2)/2]+res[(len1+len2)/2-1])/2;
        }
    }
}

升级代码：

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    int len = m + n;
    // left用来保存上一次遍历的结果，right表视当前遍历的结果。因为偶数时：需要两个值
    int left = -1, right = -1;
    // aStart指向此时A数组的位置，bStart指向此时B数组的位置
    int aStart = 0, bStart = 0;
    for (int i = 0; i <= len / 2; i++) {
        // 每次开始新的一边遍历时，保存上次的遍历结果
        left = right;
        // 数组A指针aStart后移的条件：aStart没有到A的最后，此时A位置的数字小于B位置的数字。此时要判断B的指针bStart是否越界，如果越界的话就不去判断此时A位置的值与B位置的值的大小，而是继续遍历A当前位置的值。
        if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
            right = A[aStart++];
        } else {
            right = B[bStart++];
        }
    }
    if ((len & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}

参考链接：

(97条消息) 寻找两个正序数组的中位数_寒酥-的博客-CSDN博客_寻找两个正序数组的中位数