最长回文子序列

题目描述

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：输入：nums1 = [1,3], nums2 = [2] 输出：2.00000

示例 2：输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000

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

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

示例 5：输入：nums1 = [2], nums2 = [] 输出：2.00000  

题目链接：leetcode-cn.com/leetbook/re…

不适合的解法：

直接排序，这样做的复杂度最低也是O(n+mlog(n+m))，不合适。

解法一：

根据两组数组提前已经排序的特点。使用归并排序，然后找中位数，这里不赘述。

归并排序的相关资料： 图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 (cnblogs.com)

显然这种做法的时间复杂度降到了O(n+m)，但还不符合题目的时间复杂度。

解法二：

先从总个数为奇数出发，假设这个答案就在nums1数组中，若答案是a，在nums1中有x个数比他小。那么相应的nums2中就需要有(nums1 + nums2) / 2 - x 个数比他小这样的话才可以保证，总共有 (nums1 + nums2)/ 2个数比他小，同时肯定也存在了有(nums1 + nums2) / 2个数比他大（注意现在的总个数为奇数）。

所以我们可以先从nums1数组的(0 + nums1.length - 1)/2出发，这时候由于有 (0 + nums1.length - 1) / 2 - 1个数比它小，所以我们直接去nums2的下标(nums1 + nums2) / 2 - (0 + nums1.length - 1) / 2 - 1看一下当前下标的数是不是比它大(或等于)且并且之前的数都比它小(或等于)。

如果是，那么就找到了；如果不是，我们看一下如果nums2的下标对应的值比nums1的大，那么我们向将nums1向右二分，否则向左二分，得到新的下标i，然后去寻找nums2下标j，使得i + j 等于(nums1 + nums2) / 2。

nums1中二分结束后，如果没有找到，就去nums2里找，一样的过程。

同样的当nums1和nums2的总个数为偶数的时候，其实问题仅仅转化成了我们需要找到a1,a2两个值，使得a1在两个数组比他小的值总共有(nums1 + nums2) / 2 - 1个，a2有(nums1 + nums2) / 2个这样的情况。所以我们仅需控制上面过程中最终的i + j的和。

由于没有进行循环，直接进行的二分，所以时间复杂度降到了log(n + m)。需要注意一些边界的判断。

AC代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length == 0) {
            if(nums2.length % 2 == 0) return (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0;
            else return  nums2[nums2.length / 2];
        }
        else if(nums2.length == 0) {
            if(nums1.length % 2 == 0) return (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) / 2.0;
            else return  nums1[nums1.length / 2];
        }
        else if(((nums1.length + nums2.length) & 1) == 1)  return this.findAns(nums1, nums2, (nums1.length + nums2.length) / 2);
        else  return  (this.findAns(nums1, nums2, (nums1.length + nums2.length) / 2 - 1) + this.findAns(nums1, nums2, (nums1.length + nums2.length) / 2)) / 2.0;
    }
    public double findAns(int[] nums1, int[] nums2, int lessNum) {
        int l = 0, r = nums1.length - 1, mid;
        while(l <= r) {
            mid = (l + r) / 2;
            if(lessNum - mid > nums2.length) l =  mid + 1;
            else if (lessNum - mid < 0) r = mid - 1;
            else {
                if(lessNum - mid == nums2.length) {
                    if(nums2[lessNum - mid - 1] <= nums1[mid]) return  nums1[mid];
                    else l = mid + 1;
                }
                else if(lessNum - mid == 0) {
                    if(nums2[lessNum - mid] >= nums1[mid]) return  nums1[mid];
                    else r = mid - 1;
                }
                else if(nums2[lessNum - mid] >= nums1[mid] && nums2[lessNum - mid - 1] <= nums1[mid]) return  nums1[mid];
                else if(nums2[lessNum - mid] > nums1[mid]) l = mid + 1;
                else r = mid - 1;
            }
        }
        l = 0; r = nums2.length;
        while(l <= r) {
            mid = (l + r) / 2;
            if(lessNum - mid > nums1.length) l =  mid + 1;
            else if (lessNum - mid < 0) r = mid - 1;
            else {
                if(lessNum - mid == nums1.length) {
                    if(nums1[lessNum - mid - 1] <= nums2[mid]) return  nums2[mid];
                    else l  = mid + 1;
                }
                else if(lessNum - mid == 0) {
                    if(nums1[lessNum - mid] >= nums2[mid]) return  nums2[mid];
                    else r = mid - 1;
                }
                else if(nums1[lessNum - mid] >= nums2[mid] && nums1[lessNum - mid - 1] <= nums2[mid]) return  nums2[mid];
                else if(nums1[lessNum - mid] > nums2[mid]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return  0.0;
    }
}

上面的很多步骤写的比较冗余，有兴趣的小伙伴可以再精简一下。

总结：思考问题从局部出发，亦可以从答案往回推，把一些条件看的更透彻和普通化。

如果有不懂的小伙伴或者觉得这篇题解不是很到位，都可以再评论区留言，希望和大家一起进步！