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

水深无声 2022-10-26 14:05 192阅读 0赞

# 题目： #

[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

4. 	寻找两个正序数组的中位数
    	给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
    	请你找出并返回这两个正序数组的中位数。
    
    进阶：你能设计一个时间复杂度为 O(log(m+n)) 的算法解决此问题吗？
    
    示例 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
    
    提示：
    	nums1.length == m
    	nums2.length == n
    	0 <= m <= 1000
    	0 <= n <= 1000
    	1 <= m + n <= 2000
    	-10^6 <= nums1[i], nums2[i] <= 10^6

# 解： #

笨比行为大赏：

首先是最容易想到的，把两个数组合并起来，然后取中位数。这个就忽略了。

总长度固定，那么要找的中位数的索引也能确定下来，然后用两个指针分别指向两个数组的位置，一个一个往后找，循环特定的次数，然后总个数分别为奇偶数做不同的处理，最后取数，就得到了结果，这个方法的复杂度应该是O(m+n)。空间复杂度为O(1)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]

publicstatic double findMedianSortedArrays(int[] nums1, int[] nums2) { 
        double result = 0;
    
        int length = nums1.length + nums2.length;
    
        int point1 = 0;
        int point2 = 0;
    
        if (length % 2 == 0) { 
            // 总数为偶数时
            for (int i = 0; i < length / 2 - 1; i++) { 
                if (point2 == nums2.length) { 
                    point1++;
                } else if (point1 == nums1.length) { 
                    point2++;
                } else if (nums2[point2] <= nums1[point1]) { 
                    point2++;
                } else if (nums1[point1] < nums2[point2]) { 
                    point1++;
                }
            }
            for (int i = 0; i < 2; i++) { 
                if (point2 == nums2.length) { 
                    result += nums1[point1];
                    point1++;
                } else if (point1 == nums1.length) { 
                    result += nums2[point2];
                    point2++;
                } else if (nums1[point1] <= nums2[point2]) { 
                    result += nums1[point1];
                    point1++;
                } else if (nums2[point2] < nums1[point1]) { 
                    result += nums2[point2];
                    point2++;
                }
            }
            result = result / 2;
        } else { 
            // 总数为奇数时
            for (int i = 0; i < length / 2; i++) { 
                if (point2 == nums2.length) { 
                    point1++;
                } else if (point1 == nums1.length) { 
                    point2++;
                } else if (nums2[point2] <= nums1[point1]) { 
                    point2++;
                } else if (nums1[point1] < nums2[point2]) { 
                    point1++;
                }
            }
            if (point2 == nums2.length) { 
                result += nums1[point1];
                point1++;
            } else if (point1 == nums1.length) { 
                result += nums2[point2];
                point2++;
            } else if (nums1[point1] <= nums2[point2]) { 
                result += nums1[point1];
                point1++;
            } else if (nums2[point2] < nums1[point1]) { 
                result += nums2[point2];
                point2++;
            }
        }
        return result;
    }

非常笨的方法，没想到用时还不是倒数，中间要注意数组越界和大于小于号的问题，其他的就没啥了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]  
但是题目中很明显的给出了要求为时间复杂度O(log(m+n))，基本可以确定要用二分法来实现。

看了看题解，放弃。

Over！

[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20221024/dbc7111a661440d880b52aeb7e4b2ac6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]: /images/20221024/d8d3b5a89b834ed6a59e23d89b2d3c96.png