LeetCode 4.寻找两个中序数组的中位数

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

思路：

1. 二分查找标记位
2. 计算中位数

细节：

if (nums1.size() > nums2.size())
    return findMedianSortedArrays(nums2, nums1);

首先比较两个数组的大小，确保后续 nums1 的长度总是小于等于 nums2 的长度

int m = nums1.size();
int n = nums2.size();
int l = 0, r = m, halfLen = (m + n + 1) / 2;

计算出合并后数组左半部分的长度 halfLen，+1可确保合并后总长度为奇数时halfLen为中位数

while (l <= r) 
{
    int mid1 = (l + r) / 2;
    int mid2 = halfLen - mid1;

    if (mid1 < r && nums1[mid1] < nums2[mid2 - 1])
        l = mid1 + 1;
    else if (mid1 > l && nums1[mid1 - 1] > nums2[mid2])
        r = mid1 - 1;
    else
    {
        // 后续处理中位数
    }
}

通过二分法不断调整 mid1（ nums1 的标记位）来找到合适的划分点，并在每次循环中，根据当前的 mid1 计算出对应的 mid2（ nums2 的标记位）保证 mid1 + mid2 = halfLen

mid1和mid2的 )左边 即左半部分
mid1和mid2的 右边( 即右半部分 

• 当 mid1 < r 且 nums1[mid1] < nums2[mid2 - 1] 时，意味着当前 nums1 中划分位置 mid1 处的值太小了，导致 nums1 左半部分的最大值小于 nums2 右半部分的最小值，所以需要将 l（左边界）向右移动，即增大 mid1 的值，尝试新的划分。
• 当 mid1 > l 且 nums1[mid1 - 1] > nums2[mid2] 时，说明当前 nums1 中划分位置 mid1 处的值太大了，导致 nums1 右半部分的最小值小于 nums2 左半部分的最大值，所以需要将 r（右边界）向左移动，即减小 mid1 的值，再尝试新的划分。

当上述两个调整边界的条件都不满足时，说明找到了合适的划分点，进入后续计算中位数的逻辑。

---

int maxL = 0;
if (mid1 == 0) 
    maxL = nums2[mid2 - 1];
else if (mid2 == 0) 
    maxL = nums1[mid1 - 1];
else
    maxL = max(nums1[mid1 - 1], nums2[mid2 - 1]);

if ((m + n) % 2 == 1)
    return maxL;

• 左半部分最大值计算：
  • 初始化 maxL 存储合并后数组左半部分的最大值。
  • 如果 mid1 为 0，说明 nums1 的左半部分没有元素，那么当前左半部分最大值就是 nums2 中对应划分位置 mid2 - 1 处的元素。
  • 如果 mid2 为 0，说明 nums2 的左半部分没有元素，那么当前左半部分最大值就是 nums1 中对应划分位置 mid1 - 1 处的元素。
  • 否则，取 nums1[mid1 - 1] 和 nums2[mid2 - 1] 中的较大值作为左半部分的最大值，这是因为合并后有序数组左半部分的最大值必然是这两个值中的较大者。
• 根据总长度奇偶性处理返回值：
  • 如果 (m + n) % 2 == 1，即合并后的数组长度为奇数，此时中位数就是左半部分的最大值 maxL，直接返回该值即可。

int minR = 0;
if (mid1 == m)
    minR = nums2[mid2];
else if (mid2 == n)
    minR = nums1[mid1];
else
    minR = min(nums1[mid1], nums2[mid2]);

return (maxL + minR) / 2.0;

• 右半部分最小值计算（数组长度为偶数时需要）：
  • 初始化 minR 存储合并后数组右半部分的最小值。
  • 如果 mid1 等于 m，意味着 nums1 的右半部分没有元素，那么右半部分最小值就是 nums2 中对应划分位置 mid2 处的元素。
  • 如果 mid2 等于 n，意味着 nums2 的右半部分没有元素，那么右半部分最小值就是 nums1 中对应划分位置 mid1 处的元素。
  • 否则，取 nums1[mid1] 和 nums2[mid2] 中的较小值作为右半部分的最小值，这因为合并后有序数组右半部分的最小值必然是这两个值中的较小者。
• 最终返回中位数（数组长度为偶数时）：
  • 当合并后的数组长度为偶数时，中位数是左半部分最大值 maxL 和右半部分最小值 minR 的平均值，所以返回 (maxL + minR) / 2.0。

例如：

 

总代码：

class Solution 
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        if (nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);

        int m = nums1.size();
        int n = nums2.size();
        int l = 0, r = m, halfLen = (m + n + 1) / 2;

        while (l <= r) 
        {
            int mid1 = (l + r) / 2;//nums1的mid
            int mid2 = halfLen - mid1;//nums2的mid

            if (mid1 < r && nums1[mid1] < nums2[mid2 - 1])
                l = mid1 + 1;//nums1[mid1]小于nums2[mid2 - 1]，说明mid1的值偏小了，需要将l向右移动
            else if (mid1 > l && nums1[mid1 - 1] > nums2[mid2])
                r = mid1 - 1;//nums1[mid1 - 1]大于nums2[mid2]，说明mid1的值偏大了，需要将r向左移动
            else
            {
                //处理左半部分最大值
                int maxL = 0;
                if (mid1 == 0) //当mid1为 0 时，左半部分最大值就是nums2[mid2 - 1]
                    maxL = nums2[mid2 - 1];
                else if (mid2 == 0) //当mid2为 0 时，左半部分最大值就是nums1[mid1 - 1]
                    maxL = nums1[mid1 - 1];
                else
                    maxL = max(nums1[mid1 - 1], nums2[mid2 - 1]);//取nums1[mid1 - 1]和nums2[mid2 - 1]中的较大值

                if ((m + n) % 2 == 1)//奇数则直接取左半部分最大值
                    return maxL;

                //处理右半部分最小值
                int minR = 0;
                if (mid1 == m)//当mid1为 m 时，右半部分最小值就是nums2[mid2]
                    minR = nums2[mid2];
                else if (mid2 == n)//当mid2为 n 时，右半部分最小值就是nums1[mid1]
                    minR = nums1[mid1];
                else
                    minR = min(nums1[mid1], nums2[mid2]);//取nums1[mid1]和nums2[mid2]中的较小值

                return (maxL + minR) / 2.0;
            }
        }
        return 0;
    }
};

 

原文地址：https://blog.csdn.net/weixin_73225182/article/details/144010336

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！