LeetCode[4] - 两个排序数组的中位数

~~

好久没写一些乱七八糟的东西了，两个月前裸辞离开了大连，成功加入杭漂大家庭，很顺利的进入到了一家“独角兽”~~ 只面了这一家，拿了offer就在杭州玩了一个星期就入职了。上家拖欠的工资依旧没有结算。
来这主要负责基于socketio的IM部分功能开发~~ 最近开发任务不是很重就刷刷leetcode，解闷······
如果有怎么不对的地方或者其他想法可以一起讨论哟 ~~ 楼主玻璃心 勿喷的太严重~~

正文

之前一直刷的都是简单、中等，突然发现个困难level的还有点小激动。
题目是这样的：

题

乍一看很简单，当然最容易想到的解法就是两个数组合并成一个然后找结果~但是既然是算法题那是否有更优的选择呢？

心路历程

首先，根据这两个数组我们能获取到的已知信息：

• 数组总长度：size=nums1.length+nums2.length
• 中位数的位置：size/2或者size/2,size/2-1(后者需要取平均数）
• 是否需要取平均数：size % 2 == 0
  这是目前比较直观的信息。
  假如人工去处理这个问题会怎么个过程？
• 拿到两者第一项比较
• 选择较小的一方，拿较小一方的下一项和较大一方的第一项比较
• 选择较小的一方，拿较小一方的下一项和较大一方的当前项比较
• 递归中···当取得size/2项停止递归
• 若有一方数组无下一项，那直接在另一方数组中查找
  思路有了那么代码就是翻译的过程····

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;//数组总长度
        int bingo = size / 2;//中位数所在项
        int index1 = 0;//nums1遍历下标位置
        int index2 = 0;//nums2遍历下标位置
        double pre = 0;//当前结果前一项，用于算平均数
        double now = 0;//当前结果
        int[] currentArray;//当前遍历数组
        int currentIndex;//当前遍历下标
        if (size == 0) {
            return 0;
        }
        for (int i = 0; i <= bingo; i++) {
            pre = now;
            if (nums1.length <= index1) {//nums1无下一项，直接从nums2中取中位数
                int k = index2 + bingo - i;
                now = nums2[k];
                if (k > 0 && pre < nums2[k - 1]) {//pre在nums1中或在nums2中
                    pre = nums2[k - 1];
                }
                break;
            } else if (nums2.length <= index2) {//同上
                int k = index1 + bingo - i;
                now = nums1[k];
                if (k > 0 && pre < nums1[k - 1]) {
                    pre = nums1[k - 1];
                }
                break;
            }
            if (nums1[index1] <= nums2[index2]) {//选取当前项中较小的数组，下标后移
                currentArray = nums1;
                currentIndex = index1;
                index1++;
            } else {
                currentArray = nums2;
                currentIndex = index2;
                index2++;
            }
            now = currentArray[currentIndex];
        }
        return size % 2 == 0 ? (now + pre) / 2 : now;
    }

因为智商不够只能写写“面向过程”算法，但是做出来还是蛮有成就感的~~

运行

运行结果统计

抱着学习的心态，我复制了速度排行第一的源码，很简洁：

    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        double res = (findKth(nums1, nums2, left) + findKth(nums1, nums2, right)) / 2.0;
        return res;
    }

    int findKth(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        if (m > n) return findKth(nums2, nums1, k);
        if (m == 0) return nums2[k - 1];
        if (k == 1) return Math.min(nums1[0], nums2[0]);
        int i = Math.min(m, k / 2), j = Math.min(n, k / 2);
        if (nums1[i - 1] > nums2[j - 1]) {
            return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j);
        } else {
            return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k - i);
        }

一看就是递归大佬，但递归的效率应该是低于遍历的吧，而且又有大量的Arrays.copyOfRange于是我打算搞点测试用例pk一下,size为数组长度,max为数组项最大值，数组项随机生成：

测试用例:size,max	递归（ms)	非递归(ms)
nums1:10000000,10000; nums2: 100,10000	562	22
nums1:10000000,10000000; nums2: 10000000,10000000	619	63
nums1:10000000,100; nums2: 10000000,10	505	29

单纯从时间上来看果然递归效率并不是特别好，还有很多测试用例我就不放表格里了，简书的markdown真的是有待完善···

总结

这么来看leetcode的统计也不是特别准确，仅供参考吧。这道算法题难度定位可能也不是特别准确，之前做的简单level难度上确实有超过这个的，可能每个人擅长和思考方式不一样吧。先写到这，工作啦~
按照时间复杂度来计算 后者却是完全符合题意。我的时间复杂度稍微高一点…