~~
好久没写一些乱七八糟的东西了，两个月前裸辞离开了大连，成功加入杭漂大家庭，很顺利的进入到了一家“独角兽”~~ 只面了这一家，拿了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难度上确实有超过这个的，可能每个人擅长和思考方式不一样吧。先写到这，工作啦~
按照时间复杂度来计算 后者却是完全符合题意。我的时间复杂度稍微高一点…
网友评论