当前位置：首页 > 牛客 > 牛客231765题解析：高效求解两个有序数组中位数的分治算法（附代码详解）

牛客231765题解析：高效求解两个有序数组中位数的分治算法（附代码详解）

6小时前

一、题目解读

牛客231765题要求求解两个有序数组的中位数。给定两个长度分别为m和n的有序数组arr1和arr2，需找到合并后数组的中位数。中位数定义为排序后位于中间位置的元素，若总长度为奇数则直接取中间值，偶数则取中间两个元素的平均值。本题的核心在于如何在O(log(m+n))时间内高效找到这个中位数，避免直接合并排序带来的O(m+n)复杂度。

二、解题思路

采用分治法，通过二分查找分割点来减少比较次数。关键思想是：在两个数组中找到合适的分割点（即arr1的第k1位置和arr2的第k2位置），使得分割后的左右两部分元素数量总和满足中位数的定义。通过比较分割点两侧的最大值（左部分）与最小值（右部分），判断当前分割是否满足条件，进而缩小搜索范围。通过二分法，将时间复杂度控制在O(log(m+n))。

三、解题步骤详解

1. 确定基准数组：确保arr1为较短数组，若arr2更短则交换，减少后续循环次数。

2. 二分查找分割点：在arr1中通过二分法寻找分割点partition1，根据总长度计算arr2的分割点partition2。

3. 处理边界情况：当partition1或partition2为0或数组末尾时，特殊处理边界值（如INT_MIN/INT_MAX），避免越界。

4. 判断分割有效性：比较两侧的最大值（左）与最小值（右），若满足maxLeft1 ≤ minRight2 且 maxLeft2 ≤ minRight1，则找到正确分割点。

5. 递归调整：若分割不满足条件，根据大小关系调整二分范围（缩小左侧或右侧），继续循环查找。

6. 返回结果：最终合并数组的上中位数为两个分割点左侧的最大值（即max(maxLeft1, maxLeft2)）。

四、代码与注释

class Solution {
public:
    int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
        // 确保arr1是较短的数组
        if (arr1.size() > arr2.size()) {
            return getUpMedian(arr2, arr1); // 递归交换数组
        }
        
        int m = arr1.size();
        int n = arr2.size();
        int total = m + n;
        int low = 0, high = m; // 二分范围初始化
        
        while (low <= high) {
            int partition1 = (low + high) / 2; // 当前分割点
            int partition2 = (total + 1) / 2 - partition1; // 对应arr2的分割点
            
            // 处理边界情况
            int maxLeft1 = (partition1 == 0)? INT_MIN : arr1[partition1 - 1];
            int minRight1 = (partition1 == m)? INT_MAX : arr1[partition1];
            
            int maxLeft2 = (partition2 == 0)? INT_MIN : arr2[partition2 - 1];
            int minRight2 = (partition2 == n)? INT_MAX : arr2[partition2];
            
            // 找到正确的分割点
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 返回上中位数（合并数组中间位置的较大值）
                return max(maxLeft1, maxLeft2);
            } 
            else if (maxLeft1 > minRight2) {
                // 分割点需要左移（缩小右侧范围）
                high = partition1 - 1;
            } 
            else {
                // 分割点需要右移（扩大右侧范围）
                low = partition1 + 1;
            }
        }
        
        return -1; // 理论上不会执行到这里
    }
};

注释解析：通过递归交换数组长度确保arr1较短，利用二分法动态调整分割点，结合边界处理避免数组越界，最终通过比较分割点两侧的极值确定中位数位置。