LeetCode4. 寻找两个有序数组的中位数

迷南。 2023-06-10 09:25 107阅读 0赞

**题目描述：**  
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = \[1, 3\]  
nums2 = \[2\]

则中位数是 2.0  
示例 2:

nums1 = \[1, 2\]  
nums2 = \[3, 4\]

则中位数是 (2 + 3)/2 = 2.5

**解题：**  
这道题，典型的暴力破解，但是，有个时间复杂度在那里放着呐，所以啊，在这里，很明显的思路，就是开辟一个新的数组，用空间换时间，新数组可以装下原先的两个数组，然后就容易了。  
**代码：**

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int length1 = nums1.length;
            int length2 = nums2.length;
            int i = 0, j = 0, k = 0;
            int[] num = new int[length1 + length2];
            while (i < length1 && j < length2){
                if (nums1[i] < nums2[j]){
                    num[k] = nums1[i];
                    i++;
                }else {
                    num[k] = nums2[j];
                    j++;
                }
                k++;
            }
            while (i < length1){
                num[k] = nums1[i];
                i++;
                k++;
            }
            while (j < length2){
                num[k] = nums2[j];
                j++;
                k++;
            }
            int length = length1 + length2;
            double result = 0.0;
            if (length % 2 == 0){
                result = (num[length/2 - 1] + num[length/2])*1.0/2;
            }else {
                result = num[length/2];
            }
            return result;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTAxMTA1_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTAxMTA1_size_16_color_FFFFFF_t_70]: /images/20230531/f832ce8e76c74b6b8e7269d9d7883845.png