如何建立公众号的步骤,长沙百度快照优化排名,最有前景的十大行业,网片生产厂家1. 题目
见 寻找两个正序数组的中位数
2. 解题思路
首先一看到题目说是正序数组#xff0c;且时间复杂度要求在对数级别#xff0c;所以自然想到了双指针中的二分法。 首先来看一下#xff0c;假设输入是这两个数组#xff0c;那么将其逻辑合并成一个大数组的话#x…1. 题目
见 寻找两个正序数组的中位数
2. 解题思路
首先一看到题目说是正序数组且时间复杂度要求在对数级别所以自然想到了双指针中的二分法。 首先来看一下假设输入是这两个数组那么将其逻辑合并成一个大数组的话分界线左边为大数组的左边右边同理。这个数组又是升序的且原来的两个数组是升序的即L1R1 L2R2。所以在大数组中L1R2 L2R1 所以这里就得到了第一个约束切割后的中位线要满足交叉小于等于。 然后大数组的中位数呢就是从中位数左边选择一个大的数字Max(L1,L2)和右边选一个小的数字MinR1R2来进行计算。
上面的情况是刚好属于一个逻辑合并数组并且划分中位线后 满足交叉小于的情况假如像下图划分中位线后不满足交叉小于呢 因为L2R1了所以我们右移R1直到比L2大满足交叉小于等于。 这个时候会奇怪了为什么要移动nums2的中位线 因为此时我们做了一个逻辑合并数组的设想所以整个大数组中位线两边的元素应该尽量保持相同。 R1移动后nums1中位线左边有5个元素所以同理移动nums2的中位线让它的右边也有5个元素。
另外需要注意的是 1、我们默认只对nums1进行操作由nums1的操作计算出对nums2的操作。比如 假如不符合交叉小于等于那么我们就移动nums1的中位线然后由公式算出nums2的中位线即可。 2、当数组为奇数的时候我们默认把中位线划分在右边一点左边也是可以的
上面说的是两个数组都是偶数的情况假如有个数字为奇数呢 因为数组是有序的且满足交叉小于等于且奇数数组的中位数都是划分在右边的我们约定的单拎出来nums2看的话中位数是中位线左边的那个。所以最后逻辑合并大数组了中位数只要在大数组中位线左边取偏大的就行了。也就是maxL1L2
3. 代码
class Solution {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;int median1 0, median2 0;while (left right) {//确定第一个数组的分割线median1 (left right) / 2;//确定第二个数组的分割线median2 (m n 1) / 2 - median1;//数组1中位分割线左边的数int L1 (median1 0 ? Integer.MIN_VALUE : nums1[median1 - 1]);//数组1中位分割线右边的数int R1 (median1 m ? Integer.MAX_VALUE : nums1[median1]);//数组2中位分割线左边的数int L2 (median2 0 ? Integer.MIN_VALUE : nums2[median2 - 1]);//数组2中位分割线右边的数int R2 (median2 n ? Integer.MAX_VALUE : nums2[median2]);int nums_j (median2 n ? Integer.MAX_VALUE : nums2[median2]);if (L1 R2) {//不符合交叉小于等于 继续二分(左移中位线)right median1-1;} else if (L2 R1) {//不符合交叉小于等于 继续二分(右移中位线)left median1 1;} else {//将所有的数合并后如果是偶数个数中位数是中间两个数的平均值如果是奇数个数中位数是大的数return (m n) % 2 0 ? (Math.max(L1, L2) Math.min(R1, R2)) / 2.0 : Math.max(L1, L2);}}return 0.0;}}
