leetcode4：寻找两个正序数组的中位数

题目链接

leetcode

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的中位数 。
算法的时间复杂度为 O(log(m + n)) 。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    由于两个数组的长度已知，所以中位数对应两个数组的下标之和也是已知的。
    维护两个指针，初始时分别指向两个数组的下标 0 的位置，
    每次将指向较小值的指针后移一位（若一个指针已到达数组末尾，则只移动另一个数组的指针），
    直到到达中位数的位置。

    时间复杂度：O(logn)
        其中 m 和 n 分别是数组 nums1 和 nums2 的长度。
        初始时，k = (m+n)/2 或 k = (m+n)/2+1，每一轮循环将查找范围减少一半。
        因此，时间复杂度是 O(log(m+n))。
    空间复杂度：O(1)
*/
class Solution_0 {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int length = nums1.size()+nums2.size();
        if (length == 0) {
            return 0.0;
        }
        if (length % 2 == 0) {
            int left = findK(nums1, nums2, length/2);
            int right = findK(nums1, nums2, length/2+1);
            return (left + right) / 2.0;
        } else {
            return findK(nums1, nums2, length/2+1);
        }
    }

    int findK(const vector<int>& nums1, const vector<int>&nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        int i = 0, j = 0;

        while (true) {
            // 边界情况
            if (i == m) {
                return nums2[j+k-1];
            }
            if (j == n) {
                return nums1[i+k-1];
            }
            if (k == 1) {
                return min(nums1[i], nums2[j]);
            }

            // 正常情况
            int half = k/2;
            int new_i = min(i+half-1, m-1);
            int new_j = min(j+half-1, n-1);
            
            if (nums1[new_i] <= nums2[new_j]) {
                k -= new_i - i + 1;
                i = new_i + 1;
            } else {
                k -= new_j - j + 1;
                j = new_j + 1;
            }
        }
    }
};

/*
    中位数的作用：将一个集合划分为两个长度相等的子集，
    二分查找的方法来高效地定位到两个数组中的“分割点”，从而计算出中位数。

    时间复杂度：log(min(m,n))
        其中 m 和 n 分别是数组 nums1 和 nums2 的长度。
        查找的区间是 [0, m]，该区间的长度在每次循环之后减少为原来的一半，执行 logm 次循环。
        每次循环中的操作次数是常数，时间复杂度为 O(logm)。
        可能交换 nums1和 nums2，时间复杂度是 O(log(min(m,n)))。
    空间复杂度：O(1)
*/
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.size() > nums2.size()) {
            swap(nums1, nums2);
        }

        int m = nums1.size(), n = nums2.size();
        int left = 0, right = m;
        int total = (m+n+1) / 2; // 前半段长度

        while (left < right) {
            int i = (left+right+1) / 2; // nums1 划分点
            int j = total - i;          // nums2 划分点

            if (nums1[i-1] <= nums2[j]) {
                left = i; // 向右扩展
            } else {
                right = i-1; // 向左收缩
            }
        }

        int i = left;
        int j = total - i;

        // 处理边界情况，并计算中位数
        int nums1_left_max = (i == 0) ? INT_MIN : nums1[i-1];
        int nums1_right_min = (i == m) ? INT_MAX : nums1[i];
        int nums2_left_max = (j == 0) ? INT_MIN : nums2[j-1];
        int nums2_right_min = (j == n) ? INT_MAX : nums2[j];

        if ((m+n) % 2 == 1) {
            return max(nums1_left_max, nums2_left_max); // 奇数长度
        } else {
            return (max(nums1_left_max, nums2_left_max) + 
                    min(nums1_right_min, nums2_right_min)) / 2.0; // 偶数长度
        }
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums1_cases = {
        {1,3}, {1,2}, {},
    };
    vector<vector<int>> nums2_cases = {
        {2}, {3,4}, {}
    };

    for (size_t i = 0; i < nums1_cases.size(); i++) {
        auto& nums1 = nums1_cases[i];
        auto& nums2 = nums2_cases[i];

        cout << "Input: nums1 = ";
        printArray(nums1);
        cout << ", nums2 = ";
        printArray(nums2);
        cout << endl;

        double median = solution.findMedianSortedArrays(nums1, nums2);
        cout << "Output: " << median << endl;
    }

    return 0;
}