LeetCode_Subject4
题目:给定两个大小分别为m和 n的正序（从小到大）数组nums1和 nums2。请你找出并返回这两个正序数组的中位数进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？时隔好久好久，因为工作原因
耽搁了好久，也给了自己很多的思考时间（时间复杂度，空间复杂度）
看了知乎上面一个比较透彻的讲解之后 ，感觉到一丝丝灵感 但是还没完全掌握 希望可以在接下来的题目里面 运用
时间复杂度：算法的渐进时间复杂度。
大O符号表示法：
1.常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
2.对数阶O(logN)
在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。
我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
3.线性阶O(n)
for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度
4.线性对数阶O(nlogN)
将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
5.平方阶O(n2)
如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n2) 了。
6.立方阶O(n3)
O(n3)相当于三层n循环
7.K次方阶O(n^k)
O(n^k)相当于K层n循环
8.指数阶(2^n)
知乎没说 大概就非常非常大 非常非常低
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
空间复杂度 O(n)
1.空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
2.空间复杂度 O(n)
不管代码执行多少次 占用的临时空间都为n的情况
接下来研究这道题目了
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
List<Integer> integers = new ArrayList<>();
for (int i = 0; i < nums1.length; i++) {
integers.add(nums1);
}
for (int i = 0; i < nums2.length; i++) {
integers.add(nums2);
}
Collections.sort(integers);
// 这是双数
if (integers.size() % 2 == 0) {
Integer integer = new ArrayList<Integer>(integers).get(integers.size() / 2 - 1);
Integer integer1 = new ArrayList<Integer>(integers).get(integers.size() / 2);
return (integer + integer1) / 2.0;
} else {
return new ArrayList<Integer>(integers).get(integers.size() / 2).doubleValue();
}
}
基本操作最笨办法先来一个
把他们两个数组 放到一个list里面 然后按照大小排序
然后判断size size为偶数 取size/2+size/2-1 的下标然后求平均值
如果是奇数，直接找size/2的下标 就是它了
这种办法属于最笨最笨的办法 完全不符合题目中的进阶要求
我去学习了一下官方的代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 把长度较长的数组放到后面
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
// 第一个的长度
int m = nums1.length;
// 第二个的长度
int n = nums2.length;
int left = 0, right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
// 当左边 > 右边的时候 说明遍历完了
while (left <= right) {
// 前一部分包含 nums1 和 nums2
// 后一部分包含 nums1 和 nums2
// 第一个数组分割线右边下标 第一个数组左边元素个数
int i = (left + right) / 2;
// 第二个数组分割线右边下标 第二个数组左边元素个数
int j = (m + n + 1) / 2 - i;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1, nums1, nums2, nums2
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1);
int nums_i = (i == m ? Integer.MAX_VALUE : nums1);
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2);
int nums_j = (j == n ? Integer.MAX_VALUE : nums2);
// 第一个数组的左边 要小于第二个数组的右边
if (nums_im1 <= nums_j) {
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
// 左边向右
left = i + 1;
} else {
// 右边向左
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
}
数组1 长度m
数组2 长度n
我用画图的方式 一步一步执行 拆分学习
它选择把长度稍大一点的集合 放在第二个的位置，为了避免数组越界
主要的思路是这样 在int计算中3/2=12/2=1
所以我们可以规避一个问题。奇数和偶数 都可以用（m+n-1）来表示那个最中间的元素
要在脑海里把两个数组分为四个部分 第一个数组的左边+第二个数组的左边 =我们最终排列出来的最中间的那个位置 左边的全部数组
第一个数组右边+第二个数组右边=我们最终排列出来的最中间的那个位置 右边的全部数组
把握住我们的船舵 就可以开始远航
第一次开始循环的时候i和j 的位置 是指第一个数组最中间 和第二个数组最中间
我们只要找到这两个合适的位置 就找到了我们所需要的东西
然后 我们刚开始找 的位置肯定是不合适的怎么判断什么时候合适
i左边的数字一定会小于它右边的数字 要让它也小于第二个数组j右边的数字， 这才是合适的位置
如果它小于右边 那我们也不能直接断定 就是合适的位置 应该再把i往右移动，找到那个最合适的位置 它再往右走一步 就会大于j右边 那我们就找到了
当left>right的时候 我们循环完了
这个时候 在我们已经找到那个点的时候 就应该结束了 但是代码不知道我们是不是真的找到了 所以它还会一直找
每次找到合适的时候 就会记录下 i，j左边最大的 和右边最大的
它找到最合适的之后 继续移动ij 就会开始动right 不会再去动最大值最小值
这就是一个比较精妙的点
这是一个评论里面的也比较巧妙 之前看不懂写完帖子之后回头看 有点灵感
public static double 评论(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 总长度
int length = nums1.length + nums2.length;
int val1 = 0, val2 = 0, p = 0, k = 0;
// p ik j 直接从0开始一个一个往右读
while (p + k < length / 2 + 1) {
val1 = val2;
// 防止下标越界 第二个数组被读完了
if (k == n) {
val2 = nums1;
continue;
}
// p == m 也是防止下标越界 第一个数组被读完了 记录的是第二个数组
if (p == m || nums1 >= nums2) {
val2 = nums2;
} else {
val2 = nums1;
}
}
if (length % 2 == 0) {
return (double) (val1 + val2) / 2;
}
returnval2; }
原理大概是这样
两个数组从左到右依次循环还是秉着上面的原则 找最中间
每次都往前走一步 ，一直取最大值，p+k到最中间的时候 如果总长度奇数val2就是我们要的数
如果是总长度偶数 (val1+val2)/2就是我们要的结果
想象一下 把两个数组 放到一个数组里面 我们知道我们要的数 是最中间（m+n+1）/2
我们循环数组 一个一个循环 循环到最中间 我们直接就拿到值了
比较精妙的两种方法 还是官方的更diao一点
下一题学习88题 和这道题有一些相似 膜拜大佬
页:
[1]