响应式网站制作软件,网站域名备案密码,学校网站建设具体分工,炫酷的html5网站文章目录1题目理解2 二分查找解题2.1中位数的定义2.2 数组切分2.3分析条件1题目理解
输入#xff1a;2个已经排序号的int数组nums1,nums2 输出#xff1a;这两个数组合并后的中位数 要求#xff1a;m是nums1的长度#xff0c;n是nums2的长度。时间复杂度应该是O(log(mn))。…
文章目录1题目理解2 二分查找解题2.1中位数的定义2.2 数组切分2.3分析条件1题目理解
输入2个已经排序号的int数组nums1,nums2 输出这两个数组合并后的中位数 要求m是nums1的长度n是nums2的长度。时间复杂度应该是O(log(mn))。 例子: nums1 [1, 3] nums2 [2]
The median is 2.0
nums1 [1, 2] nums2 [3, 4]
The median is (2 3)/2 2.5
2 二分查找解题
这道题目如果不要求时间复杂度的话很简单。把两个数组合并。如果长度为奇数找到中间位置的下标返回该元素。如果长度是偶数则找到中间两个元素求平均值返回。要符合时间复杂度要求就要用二分。以下内容来源于力扣只看解法四。 这种解法在一刷的时候没看明白现在二刷更清楚了。知道怎么从题目描述到最终的条件。知道为什么这样做是对的。
2.1中位数的定义
中位数将一个数组分成两部分左边元素个数等于右边元素个数并且左边元素的值都小于右边元素的值。
2.2 数组切分
在数组中我们在任意位置i将数组切分为2部分。
由于数组A中有m个元素所以数组A有m1种切分方法。 i∈[0,m]i\in[0,m]i∈[0,m],那么 len(leftA)i,len(rightA)m−ilen(left_A)i,len(right_A)m-i len(leftA)i,len(rightA)m−i
采用同样的方式在位置j将数组B切分为两部分。 j∈[0,n]j\in[0,n]j∈[0,n],那么 len(leftB)j,len(rightB)n−jlen(left_B)j,len(right_B)n-j len(leftB)j,len(rightB)n−j
将left_A和left_B一起合并形成left_part将right_A和right_B一起合并形成right_part。
当A和B的长度是偶数的时候如果len(left_part)len(right_part)并且max(left_part)min(right_part) 那么中位数max(left_part)min(right_part)2中位数\dfrac{max(left\_part)min(right\_part)}{2}中位数2max(left_part)min(right_part)
当A和B的长度是奇数的时候如果len(left_part)len(right_part)1并且max(left_part)min(right_part)那么 中位数max(left_part)中位数max(left\_part)中位数max(left_part)
2.3分析条件
对于奇偶情况不同长度条件不一样我们可以做合并。要想得到中位数需要符合上面两个条件。这两个条件可以这样理解。
1 ijm-in-j (mn为偶数)或者 ijm-in-j1(mn为奇数)。等号左侧是前一部分元素个数等号右侧是后一部分元素个数。将ij都转到等号左边做变换得到ijmn12ij\dfrac{mn1}{2}ij2mn1。 具体过程是mn为偶数,对于ijm-in-j ,得到2*(ij)mn进一步ijmn2ij\dfrac{mn}{2}ij2mn因为mn为偶数其实mn2mn12\dfrac{mn}{2}\dfrac{mn1}{2}2mn2mn1。因为这里取的是整除所以1不会影响结果。例如422{\dfrac{4}{2}2}242,415522{\dfrac{5}{2}2}252。所以此时ijmn12ij\dfrac{mn1}{2}ij2mn1
mn为奇数, ijm-in-j1,得到2*(ij)mn1,进一步得到ijmn12ij\dfrac{mn1}{2}ij2mn1。 所以条件1就是ijmn12ij\dfrac{mn1}{2}ij2mn1
2 0im0im0im,0jn0jn0jn。如果我们规定mn那么对于任意的i∈[0,m]i \in[0,m]i∈[0,m],都有jmn12−i∈[0,n]j\dfrac{mn1}{2}-i \in[0,n]j2mn1−i∈[0,n]。这是因为不能让j是负数。可以举一个反例。例如m10,n4,当i9的时候j7-9就是负数了。
3 max(left_part)min(right_part)的等价条件是A[i-1]B[j]并且B[j-1]A[i]。我们可以对该条件做进一步分析。 首先因为数组切分可能切在数组开始也可能切在数组末尾。也就是说i0也有im,j0,jn的情况。这个时候我们假设A[-1]B[-1]−∞-\infty−∞A[m1]B[n1]∞\infty∞。这样可以保证结果值不受影响。如果i0那么leftA−∞left_A{-\infty}leftA−∞最大值肯定来源于leftBleft_BleftB。所以结果不影响。其他同理。
接着我们需要证明A[i-1]B[j]并且B[j-1]A[i] 等价于找到最大的i使得A[i-1]B[j]jmn12−ij\dfrac{mn1}{2}-ij2mn1−i。 这是因为当i从0到m主键增加j会从n到0逐渐减小A[i-1]递增B[j]逐渐递减。总会找到一个最大的i使得A[i-1]B[j]。 如果i是最大的那说明i1不满足说明A[i]B[j-1]也就是说B[j-1]A[i]。和原来的条件要求是一样的。
因此我们可以在[0,m]上找到最大的i使得A[i-1]B[j],那么i,j就是切分点。前一部分元素的最大值以及后一部分的最小值才可能是数组的中位数。
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m nums1.length;int n nums2.length;//第一个数组一定是短的这是因为 我们要保证i和j都是大于0的数。因为lr的限制那么如果im的时候j就一定为负数了。if(mn){return findMedianSortedArrays(nums2,nums1);}int l 0, r m;//A中元素有m个有m1种划分方法。这里的i表示leftA有几个元素。int median10,median20;while(lr){int i (lr)1;int j (mn1)/2-i;int leftA (i0?nums1[i-1]:Integer.MIN_VALUE);int rightA (im?nums1[i]:Integer.MAX_VALUE);int leftB (j0?nums2[j-1]:Integer.MIN_VALUE);int rightB (jn?nums2[j]:Integer.MAX_VALUE);if(leftArightB){median1 Math.max(leftA,leftB);median2 Math.min(rightA,rightB);l i1;}else{r i-1;}}return (mn)%20?(median1median2)/2.0:median1;}
}
