网站建设公司怎样拓展网站业务,地方建立网站做SEM,百度百科词条创建入口,百度推广后台登录首页【问题描述】[困难]
给定两个大小为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出这两个正序数组的中位数#xff0c;并且要求算法的时间复杂度为 O(log(m n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 [1, 3]
nums2 [2]则…【问题描述】[困难]
给定两个大小为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出这两个正序数组的中位数并且要求算法的时间复杂度为 O(log(m n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 [1, 3]
nums2 [2]则中位数是 2.0
示例 2:nums1 [1, 2]
nums2 [3, 4]来源力扣LeetCode
链接https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
【解答思路】
1. 数组合并
两个数组合并两个有序数组的合并也是归并排序中的一部分。然后根据奇数还是偶数返回中位数 时间复杂度O(NM) 空间复杂度O(1)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {int[] nums;int m nums1.length;int n nums2.length;nums new int[m n];if (m 0) {if (n % 2 0) {return (nums2[n / 2 - 1] nums2[n / 2]) / 2.0;} else {return nums2[n / 2];}}if (n 0) {if (m % 2 0) {return (nums1[m / 2 - 1] nums1[m / 2]) / 2.0;} else {return nums1[m / 2];}}int count 0;int i 0, j 0;while (count ! (m n)) {if (i m) {while (j ! n) {nums[count] nums2[j];}break;}if (j n) {while (i ! m) {nums[count] nums1[i];}break;}if (nums1[i] nums2[j]) {nums[count] nums1[i];} else {nums[count] nums2[j];}}if (count % 2 0) {return (nums[count / 2 - 1] nums[count / 2]) / 2.0;} else {return nums[count / 2];}
}
2. 双指针 时间复杂度O(NM) 空间复杂度O(1)
public double findMedianSortedArrays(int[] A, int[] B) {int m A.length;int n B.length;int len m n;int left -1, right -1;int aStart 0, bStart 0;for (int i 0; i len / 2; i) {left right;if (aStart m (bStart n || A[aStart] B[bStart])) {right A[aStart];} else {right B[bStart];}}if ((len 1) 0)return (left right) / 2.0;elsereturn right;
}
3. 求第 k 小数 k/2 时间复杂度O(log(mn) 空间复杂度O(1)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n nums1.length;int m nums2.length;int left (n m 1) / 2;int right (n m 2) / 2;//将偶数和奇数的情况合并如果是奇数会求两次同样的 k 。return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 end1 - start1 1;int len2 end2 - start2 1;//让 len1 的长度小于 len2这样就能保证如果有数组空了一定是 len1 if (len1 len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);if (len1 0) return nums2[start2 k - 1];if (k 1) return Math.min(nums1[start1], nums2[start2]);int i start1 Math.min(len1, k / 2) - 1;int j start2 Math.min(len2, k / 2) - 1;if (nums1[i] nums2[j]) {return getKth(nums1, start1, end1, nums2, j 1, end2, k - (j - start2 1));}else {return getKth(nums1, i 1, end1, nums2, start2, end2, k - (i - start1 1));}}
4. 中位数 用完 长度相等 时间复杂度O(N) 空间复杂度O(1)
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int leftLength nums1.length;int rightLength nums2.length;// 为了保证第一个数组比第二个数组小(或者相等)if (leftLength rightLength) {return findMedianSortedArrays(nums2, nums1);}// 分割线左边的所有元素需要满足的个数 m (n - m 1) / 2;// 两个数组长度之和为偶数时当在长度之和上1时由于整除是向下取整所以不会改变结果// 两个数组长度之和为奇数时按照分割线的左边比右边多一个元素的要求此时在长度之和上1就会被2整除会在原来的数//的基础上1于是多出来的那个1就是左边比右边多出来的一个元素int totalLeft (leftLength rightLength 1) / 2;// 在 nums1 的区间 [0, leftLength] 里查找恰当的分割线// 使得 nums1[i - 1] nums2[j] nums2[j - 1] nums1[i]int left 0;int right leftLength;// nums1[i - 1] nums2[j]// 此处要求第一个数组中分割线的左边的值 不大于(小于等于) 第二个数组中分割线的右边的值// nums2[j - 1] nums1[i]// 此处要求第二个数组中分割线的左边的值 不大于(小于等于) 第一个数组中分割线的右边的值// 循环条件结束的条件为指针重合即分割线已找到while (left right) {// 二分查找此处为取第一个数组中左右指针下标的中位数决定起始位置// 此处1首先是为了不出现死循环即left永远小于right的情况// left和right最小差距是1此时下面的计算结果如果不加1会出现i一直left的情况而1之后i才会right// 于是在lefti的时候可以破坏循环条件其次下标1还会保证下标不会越界因为1之后向上取整保证了// i不会取到0值即i-1不会小于0// 此时i也代表着在一个数组中左边的元素的个数//1 防止死循环int i left (right - left 1) / 2;// 第一个数组中左边的元素个数确定后用左边元素的总和-第一个数组中元素的总和第二个元素中左边的元素的总和// 此时j就是第二个元素中左边的元素的个数int j totalLeft - i;// 此处用了nums1[i - 1] nums2[j]的取反当第一个数组中分割线的左边的值大于第二个数组中分割线的右边的值// 说明又指针应该左移即-1if (nums1[i - 1] nums2[j]) {// 下一轮搜索的区间 [left, i - 1]right i - 1;// 此时说明条件满足应当将左指针右移到i的位置至于为什么是右移请看i的定义} else {// 下一轮搜索的区间 [i, right]left i;}}// 退出循环时left一定等于right所以此时等于left和right都可以// 为什么left一定不会大于right?因为lefti。// 此时i代表分割线在第一个数组中所在的位置// nums1[i]为第一个数组中分割线右边的第一个值// nums[i-1]即第一个数组中分割线左边的第一个值int i left;// 此时j代表分割线在第二个数组中的位置// nums2[j]为第一个数组中分割线右边的第一个值// nums2[j-1]即第一个数组中分割线左边的第一个值int j totalLeft - i;// 当i0时说明第一个数组分割线左边没有值为了不影响// nums1[i - 1] nums2[j] 和 Math.max(nums1LeftMax, nums2LeftMax)// 的判断所以将它设置为int的最小值int nums1LeftMax i 0 ? Integer.MIN_VALUE : nums1[i - 1];// 等i第一个数组的长度时说明第一个数组分割线右边没有值为了不影响// nums2[j - 1] nums1[i] 和 Math.min(nums1RightMin, nums2RightMin)// 的判断所以将它设置为int的最大值int nums1RightMin i leftLength ? Integer.MAX_VALUE : nums1[i];// 当j0时说明第二个数组分割线左边没有值为了不影响// nums2[j - 1] nums1[i] 和 Math.max(nums1LeftMax, nums2LeftMax)// 的判断所以将它设置为int的最小值int nums2LeftMax j 0 ? Integer.MIN_VALUE : nums2[j - 1];// 等j第二个数组的长度时说明第二个数组分割线右边没有值为了不影响// nums1[i - 1] nums2[j] 和 Math.min(nums1RightMin, nums2RightMin)// 的判断所以将它设置为int的最大值int nums2RightMin j rightLength ? Integer.MAX_VALUE : nums2[j];// 如果两个数组的长度之和为奇数直接返回两个数组在分割线左边的最大值即可if (((leftLength rightLength) % 2) 1) {return Math.max(nums1LeftMax, nums2LeftMax);} else {// 如果两个数组的长度之和为偶数返回的是两个数组在左边的最大值和两个数组在右边的最小值的和的二分之一// 此处不能被向下取整所以要强制转换为double类型return (double) ((Math.max(nums1LeftMax, nums2LeftMax) Math.min(nums1RightMin, nums2RightMin))) / 2;}}
}【总结】
1. 二分查找法 log复杂度
2.边界复杂 多种情况 脑袋清晰
3.时间算法复杂度可以让简单题变复杂题
转载链接https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/ 参考视频与评论https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
