[数据结构与算法]LeetCode-Day1-题目：腾讯精选50道-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

关键字：数组、二分查找、分治
自己的代码：
解法1：合并然后排序，判断奇偶性，得到下标并查询到结果

int length = nums1.length + nums2.length;
        double res = 0.0;
        //将两个数组添加到list
        List<Integer> nums = new ArrayList<>();
        for(int i=0;i<nums1.length;i++){
            nums.add(nums1[i]);
        }
        for(int i=0;i<nums2.length;i++){
            nums.add(nums2[i]);
        }

        //集合类工具进行排序
        Collections.sort(nums);
        //根据长度奇偶性返回中位数
        if(length%2>0){
            res = nums.get(length/2);
        }
        else {
            res = (nums.get(length/2)+nums.get(length/2 -1))/2.0;
        }
        return res;

解题思路：

合并两个数组，排序，然后根据奇偶性返回中位数。想的还是太简单了，如果用这种方法，那有点愧对它的困难标签了，我直接选择学习官方题解。

解法2：双指针法，找到第k小的元素，k为len/2，然后根据奇偶性判断返回第k小的值或者第k和第k-1两者平均值。

int len = nums1.length + nums2.length;
        int p1 = 0,p2 = 0;          //定义双指针，分别指向两个数组的开头
        int key = 0;        //已剔除的个数
        int pre = 0,current = 0;        //记录前一位置的值和当前位置的值
        while (p1<nums1.length || p2<nums2.length ){
            int tmp1 = p1>=nums1.length?Integer.MAX_VALUE:nums1[p1];
            int tmp2 = p2>=nums2.length?Integer.MAX_VALUE:nums2[p2];

            if(key=len/2 ){
                current = tmp1<tmp2?tmp1:tmp2;      //如果已经到达第len/2个元素，则取两个数组目前指针位置较小的那个
                break;
            }
            //pre取两个数组指针位较小的值，并将对应数组的指针向后移动一位
            if(tmp1<=tmp2){
                pre = nums1[p1];
                p1 ++;
            }
            else {
                pre = nums2[p2];
                p2 ++;
            }
            //剔除元素个数累加
            key ++;
        }
        //奇偶判断，若为偶数，返回pre和current的平均数；若为奇数，则返回current当前的值
        return len%2==0?(pre+current)/2.0:current;

官方题解：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

解题思路：

求得第k小个元素的二分搜索优化方法，将时间复杂度从O(m+n)优化到O(log(m+n))：
通常求两个数组合并后的第k小个元素(k=len/2)的思路为，一起对两个数组进行遍历查询，如上述的双指针法求解，但时间复杂度还是无法达到O(log(m+n))的境界，要满足log，则必须引入二分查询的思想，于是对两个数组第k/2个元素进行比较，由于都为正序数组，所以可以很好的对前k/2 -1个元素进行大小判断，采用递归的方法求解:
（1）递归终止条件：k=1，即求得两个数组第1小的元素，所以返回两个数组起始位较小的那个，Min(nums1[start],nums2[start])
（2）如果两个数组长度不同，总会有个数组先遍历完，当遍历到某个数组为空时，直接返回另一个非空数组的起始位开始第k个元素，即nums2[start+k-1]，这里做一些小处理，每次将较短的数组位置规定是num1，保证数组为空情况只会发生在nums1，然后返回nums2的第start+k-1个元素；
（3）下面是通常情况，令i = start1 + k/2-1 ，j = start2 + k/2 -1, 判断nums1[i]和 nums2[j]的大小：
如果nums1[i]<nums2[j]，则将start1赋值为i + 1，从新的start1递归，并将k-（i-start1+1)赋值给k，去除已筛掉的（i - start1+ 1)个元素；
如果nums1[i]>nums2[j]，则将start2赋值为j + 1，从新的start2递归，并将k-（j-start2+1)赋值给k，去除已筛掉的（j - start2 + 1)个元素；

总结

（1）考虑到双指针遍历的用法，分析好临界条件，各种可能存在的情况；
（2）如果时间复杂度要求为O(LogN)，考虑使用二分搜索，将问题拆分为一半一半去考虑；
（3）递归思路很重要！！！