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

- 日理万妓 2022-10-06 13:58 222阅读 0赞

给定两个大小分别为 `m` 和 `n` 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。

**示例 1：**

输入：nums1 = [1,3], nums2 = [2]
    输出：2.00000
    解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = \[1,2\], nums2 = \[3,4\]  
输出：2.50000  
解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5  
示例 3：

输入：nums1 = \[0,0\], nums2 = \[0,0\]  
输出：0.00000  
示例 4：

输入：nums1 = \[\], nums2 = \[1\]  
输出：1.00000  
示例 5：

输入：nums1 = \[2\], nums2 = \[\]  
输出：2.00000

解题思路：

1. 由于两个数组均是有序数组，中位数必处于两个数组合并后中间位置。

2.故只需要找到合并数组对应下标的数字即可。

3.借用数组合并的思路，记录数组下标。

//查找两个数组合并后，对应下标的数字
    int FindNum(int* nums1, int nums1Size, int* nums2, int nums2Size, int index)
    {
        int i = 0;
        int j = 0;
        int num;
        while (true) {
            if ((i == nums1Size) && (j == nums2Size)) {
                break;
            }
            if (i == nums1Size) {
                num = nums2[j];
                j++;
            } else if (j == nums2Size) {
                num = nums1[i];
                i++;
            } else if (nums1[i] <= nums2[j]) {
                num = nums1[i];
                i++;
            } else {
                num = nums2[j];
                j++;
            }
    
            if (i + j == index) {
                return num;
            }
        }
        return 0;
    }
    //计算中位数
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
        int mid = (nums1Size + nums2Size) / 2;
        if ((nums1Size + nums2Size) % 2 == 0) {
            return 1.0 * (FindNum(nums1, nums1Size, nums2, nums2Size, mid) + 
                FindNum(nums1, nums1Size, nums2, nums2Size, mid + 1)) / 2;
        } else {
            return FindNum(nums1, nums1Size, nums2, nums2Size, mid + 1);
        }
        //return FindNum(nums1, nums1Size, nums2, nums2Size, mid);
    }