leetcode（4）寻找正序数组中位数
点击查看原文，到达leetcode题目界面
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
int[] arr = new int[len];
System.arraycopy(nums1, 0, arr, 0, nums1.length);
System.arraycopy(nums2, 0, arr, nums1.length, nums2.length);
Arrays.sort(arr);
if (arr.length % 2 == 1) {
return arr[len / 2];
} else {
return (arr[len / 2 - 1] + arr[len / 2]) / 2.0;
}
}
}
以上是api爆破法
执行用时：3 ms
内存消耗：40.6 MBAPI爆破法的思路很简单先整合两个有序数组，然后排序。
当然也可以创建一个大数组，然后自己实现分治算法，不过Arrays.sort底层就是分治算法（真·爆破偷懒法）。
这里说明一下为什么不自己实现数组整合，因为自己创建一个大的数组，然后for将两个数组合并实际上不如直接用System.arraycopy快，而用集合的话虽然能达到效果，但是占用内存更大，而且底层也是用System.arraycopy。
做算法必然是追求时间和内存撒，所以直接api爆破法。
class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int totalLen = (m + n + 1) / 2;
int l = 0, r = m;
int i;
int j;
while (l < r) {
i = l + (r - l + 1) / 2;
j = totalLen - i;
if (nums1[i - 1] > nums2[j]) {
r = i - 1;
} else {
l = i;
}
}
i = l;
j = totalLen - i;
int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
if ((m + n) % 2 == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(i == m ? Integer.MAX_VALUE : nums1[i], j == n ? Integer.MAX_VALUE : nums2[j])) / 2.0;
}
}
}
以上是二分法
执行用时：3 ms
内存消耗：40.7 MB二分法解题思路很简单，我们将两个数组假设在一个容器中，我们画一条中位线（并不是直直的，可能某个数组全部在左边，或者全部在右边），中位线左边是一半的数字，右边是一半的数组（如果num1.len+nums2.len是奇数，就某一边+1，看自己喜欢）。
只要找到这个中位线，就能明确（而且要求时间复杂度是O(log(m+n)）确实用二分法比较贴切)
首先，将len较短的数组放在nums1，然后将nums1全员假设为中位线左边，那么nums2的部分（总数/2-nums1.len）也在中位线左边。
中位线满足条件，左边所有小于右边，所以我们只需要对比中位线的左边和右边是否符合这个条件，如果否，那么我们的中位线在nums1移动到nums1的中间索引，在nums2移动到（总数/2-nums1.len/2）索引。
如果nums1中位线左边仍然大于nums2右边，则中位线左移到(0+nums1.len/2)/2，如果nums2中位线左边大于nums1右边中位线，则中位线右移。
通过以上步骤循环，最终找出中位线，中位数就好找了。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-06-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
