两个有序数组找到中位数

假设有两个有序数组 nums1 和 nums2，长度分别为 m 和 n。要求找到这两个数组的中位数，时间复杂度要求为 O(log(m+n))。

一种思路是利用归并排序的思想，将两个有序数组合并成一个有序数组，然后找到中位数。

具体步骤如下：

1. 初始化两个指针 i 和 j，分别指向 nums1 和 nums2 的起始位置。
2. 判断两个指针所指元素的大小关系，将较小的元素加入到一个新的数组中，并将指针向后移动一位。
3. 重复步骤 2，直到任意一个指针越界。
4. 判断剩余数组的长度，将剩余的元素加入到新的数组中。
5. 找到新数组的中位数，如果新数组长度为偶数，则取中间两个数的平均值，如果长度为奇数，则取中间的数。

代码实现如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int total = m + n;
    vector<int> nums(total);

    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            nums[k++] = nums1[i++];
        } else {
            nums[k++] = nums2[j++];
        }
    }

    while (i < m) {
        nums[k++] = nums1[i++];
    }

    while (j < n) {
        nums[k++] = nums2[j++];
    }

    if (total % 2 == 0) {
        return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
    } else {
        return nums[total / 2];
    }
}

时间复杂度为 O(m+n)，不符合题目要求。可以使用二分查找的方法将时间复杂度优化到 O(log(m+n))。

具体思路如下：

1. 假设两个有序数组的长度分别为 m 和 n，将 nums1 分为两部分，前一部分包含 i 个元素，后一部分包含 m-i 个元素；将 nums2 分为两部分，前一部分包含 j 个元素，后一部分包含 n-j 个元素。
2. 如果中位数在两个数组的左半部分，那么 i 和 j 都需要向右移动；如果在右半部分，i 和 j 都需要向左移动；如果 i 和 j 恰好满足条件，则找到了中位数。
3. 不断重复步骤 2，直到找到中位数。

代码实现如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    if (m > n) {
        swap(nums1, nums2);
        swap(m, n);
    }

    int left = 0, right = m, halfLen = (m + n + 1) / 2;
    while (left <= right) {
        int i = (left + right) / 2;
        int j = halfLen - i;

        if (i < m && nums2[j-1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j-1];
            } else if (j == 0) {
                maxLeft = nums1[i-1];
            } else {
                maxLeft = max(nums1[i-1], nums2[j-1]);
            }

            if ((m + n) % 2 == 1) {
                return maxLeft;
            }

            int minRight = 0;
            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = min(nums1[i], nums2[j]);
            }

            return (maxLeft + minRight) / 2.0;
        }
    }

    return 0.0;
}

时间复杂度为 O(log(min(m,n)))。