求两个有序数组中位数

Question

第一次看到是刷王道书课后标出2011年的408正题，当时就用笔稍微写了一下思路，现在在力扣第四题看到，才发现是错误的

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int i=0,j=0,max=0;
    float mid=0;
   
    while(i+j+2<=(nums1Size+nums2Size)/2)
    {
        if(nums1[i]<=nums2[j])
    {
        i++;
        max=nums2;
    }
    else
    {
        j++;
        max=nums1;
    }
    }
    
    if((nums1Size+nums2Size)%2==0)
    mid=(nums1[i]+nums2[j])/2;
    else if((nums1Size+nums2Size)%2==1)
    mid=max;
    return mid;
}

不求匹配时间复杂度，只求代码运行正确

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

代码中存在一些问题，我将指出这些问题并提供一个修正后的版本。首先，让我们分析一下原始代码中的问题：

1. max 变量被用来存储数组指针，但在这个上下文中并不适用，因为我们需要存储数值而不是指针。
2. 当 (nums1Size + nums2Size) % 2 == 0 时，计算中位数的公式是错误的。你应该取 i 和 j 对应的值的平均值，而不是 nums1[i] 和 nums2[j] 的平均值。
3. 当 (nums1Size + nums2Size) % 2 == 1 时，中位数应该是 max 指向的那个数组的最后一个选取的元素，但这里直接返回了 max，这同样是错误的，因为 max 是一个指针。

修正后的代码如下：

#include <stdio.h>

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int i = 0, j = 0, max1 = 0, max2 = 0; // 添加 max1 和 max2 用于存储两个中位数候选值
    int totalSize = nums1Size + nums2Size;

    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] <= nums2[j]) {
            max1 = nums1[i];
            i++;
        } else {
            max1 = nums2[j];
            j++;
        }

        // 更新第二个中位数候选值
        if ((i + j + 1) == (totalSize / 2)) {
            max2 = max1;
            break;
        }

        if (nums1[i] > nums2[j]) {
            max1 = nums2[j];
            j++;
        } else {
            max1 = nums1[i];
            i++;
        }
    }

    // 如果总长度为偶数，返回两个中位数的平均值
    if (totalSize % 2 == 0) {
        return (double)(max1 + max2) / 2;
    }
    // 如果总长度为奇数，返回较大的中位数
    else {
        return (double)max1;
    }
}

int main() {
    int nums1[] = {1, 3};
    int nums2[] = {2};
    int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
    int nums2Size = sizeof(nums2) / sizeof(nums2[0]);

    double median = findMedianSortedArrays(nums1, nums1Size, nums2, nums2Size);
    printf("The median is: %.2f\n", median);

    return 0;
}

这个修正后的代码应该能正确地找到两个有序数组的中位数。注意，为了简化逻辑，这里没有处理边界情况，即一个数组为空的情况。如果需要处理这种情况，你可以在循环开始之前检查数组是否为空，并相应地调整 i 或 j 的初始值。