Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。
首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的 第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k /2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
-------简单的说，就是或者丢弃较大中位数的右区间，或者丢弃较小中位数的左区间。
-----------呵呵，自己想出来的， 可是，还是不自信， 没有code完，就去看别人的提示了。
---------------哎~~~~~~~ 踩到地雷了，以为很简单，没想到是难度为5 的题目------------
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length, n = B.length;
assert (!(n == m && n == 0)); // if both array are empty, WRONG
int[] C = null;// C point to the non-empty array, while the other is
// empty
if (m == 0) {
C = B;
} else if (n == 0) {
C = A;
}
if (C != null) { // if A is empty
return (C.length % 2 == 1) ? C[C.length / 2]
: (C[C.length / 2] + C[C.length / 2 - 1]) / 2.0;
}
// NOW neither A or B is empty
if ((m + n) % 2 == 1) {
return findKth(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1);
} else {
int leftMedian = findKth(A, 0, m - 1, B, 0, n - 1, (m + n) / 2);
int rightMedian = findKth(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1);
return (leftMedian + rightMedian) / 2.0;
}
}
private int findKth(int[] a, int lowA, int highA, int[] b, int lowB,
int highB, int k) {
// GOAL: each time, we either cut the half left of the smaller median
// or the right part of the bigger median array
if (k == 1) {
return Math.min(a[lowA], b[lowB]);
} else {
// if one array is empty
if (lowA > highA) { // A is empty, search in B
return b[lowB + k - 1];
}
if (lowB > highB) {// B is empty, search in A
return a[lowA + k - 1];
}
int midA = (lowA + highA) / 2;
int midB = (lowB + highB) / 2;
// two pointers pointing , according to the value of the median
int[] medianSmall = a;
int smallLow = lowA;
int smallMid = midA;
int smallHigh = highA;
int[] medianBig = b;
int bigLow = lowB;
int bigMid = midB;
int bigHigh = highB;
// make sure that small point to small
if (medianSmall[smallMid] > medianBig[bigMid]) {
medianSmall = b;
medianBig = a;
smallLow = lowB;
smallMid = midB;
smallHigh = highB;
bigLow = lowA;
bigMid = midA;
bigHigh = highA;
}
// check value of k with the size of their half
int smallLeftLength = smallMid - smallLow + 1;
// smallMid is counted, and != 0
int bigLeftLength = bigMid - bigLow + 1; // bigMid is counted;
if (k <= smallLeftLength + bigLeftLength) {
// discard the right part of the medianBig array
// NOTE that the length of the right part of the medianBig array
// could be ZERO.
if (bigMid < bigHigh) { // right part is not of length 0
return findKth(medianSmall, smallLow, smallHigh, medianBig,
bigLow, bigMid, k);
} else { // right part is of length 0, i.e. bigLow == bigHigh
// now,we can (imaginely) insert this value into the
// range of medianSmall array
int biggerMedian = medianBig[bigMid];// first candicates
if (k == smallLeftLength + 1) {
return (smallMid == smallHigh) ? biggerMedian : Math
.min(biggerMedian, medianSmall[smallMid + 1]);
} else {
return medianSmall[smallLow + k - 1];
}
}
} else { // discard the left part of the medianSmall array (
// length>0)
return findKth(medianSmall, smallMid + 1, smallHigh, medianBig,
bigLow, bigHigh, k - smallLeftLength);
}
}
}
}
Mistakes:
TMD: median 的定义是： If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values
1： 因为我们后来在处理一个数组结束之后，只寻找另一个数组的情况的时候。 用了一个唯一的值等于Interger.Max_VALUE。 所以， 当k == 1 时，我们要考虑Interger.MAX_VALUE 对我们的影响。 因此，不能简单得返回 Math.max(a[lowA],b[lowB]) ， 要改成代码中所示。
2: 当我面在递归函数里， 处理 k == 1的时候，忘记了先检验，是否数组不为空。
3： 当递归的时候， 需要处理一个情况， 就是， pointerSmall 的左边 和pointerBig的右边，如果为空的话，就会导致out of stack exception.
因此，需要先处理那些情况。
4： 要记得检测， 总数是奇数还是偶数--------导致的计算方法是不一样的
5: 哎呀， TMD，疯了， 就因为，当时， 也不知道怎么想的。可能是半夜，脑子不清醒。
当k==1的时候，我们应该取两个数组里面，各自第一个里的值的较小的呀。
应该是Math.min ------可是自己当时，写的是Math.max 花费了一次半值班的时间， 大约是4,5个小时的宝贵时间。 得不偿失啊。 Tiger
6： when discarding the right part of the medianBig array, we should check first the length of the to-be-discarded part.
因此这种情况下， medianBig 数组的bigHigh == bigSmall,我们就把它的值单独列出来，并对比medianSmall即可。 （否则会出现死循环调用，导致out of stack memory ，）
Learned:
1： 当 一个int 值， 例如，
int a = 3;
a/2 的值，默认还是int类型。 因此，当我们需要返回一个带小数的double类型的话，需要除以2.0
---------------------------第二遍 ---------------------------
Mistakes:
1: kth这个参数， 第一遍是按照0 based考虑的。 那么， 在对比leftCount+rightCount 和 kth的大小的时候， 就不需要加1了。 ----------(这个问题很快发现， 然后就调整了)
2：由于在 if 语句中（20行左右），写 (lowB+highB)/2] 的时候，拷贝了上面， 然后发现多了个 ‘】’， 就随手把if （这里的】 也去掉了， ） complier error, 就又随手加上了 ] ，。 结果加到/2 后面去了 。 哎， 结果 傻看了40多分钟，才弄明白。 哎， 人生阿～～～～～～～
状态不好的时候， 就不要去coding， 犯的SB错误，都会搞死我的时间
############ 3 rd pass##################
class Solution {public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n1 = nums1.size(), n2 = nums2.size();if ((n1 + n2) % 2 == 0) {return (getKth(nums1, 0, n1, nums2, 0, n2, (n1 + n2) / 2) +getKth(nums1, 0, n1, nums2, 0, n2, (n1 + n2) / 2 - 1)) /2.0;} else {return getKth(nums1, 0, n1, nums2, 0, n2, (n1 + n2) / 2);}}private:double getKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2,int s2, int e2, int k) {// k starts from 0. s1/s2 is inclusive, e1/e2 are exclusiveif (s1 >= e1)return nums2[s2 + k];if (s2 >= e2)return nums1[s1 + k];// both are validint m1 = (s1 + e1) / 2, m2 = (s2 + e2) / 2;if (nums1[m1] <= nums2[m2]) {int cLeft = m1 - s1 + m2 - s2 + 1; // exclude nums2[m2]if (cLeft >= k + 1) { // +1 since k starts from 0return getKth(nums1, s1, e1, nums2, s2, m2, k);} else {return getKth(nums1, m1 + 1, e1, nums2, s2, e2,k - (m1 - s1 + 1));}} else {return getKth(nums2, s2, e2, nums1, s1, e1, k);}}};
改进是， 倒数第二个if， 交换了nums1, nums2 两个数组，这样，少写一遍最容易出错的代码
Mistakes:
这里最容易犯的错误， 第一个if里，开始写成了 nLeft >= index
这里的核心，关键点是： m2 (which is the bigger value) is exclusive, and m1 is inclusive.
网上的解法：
不去管真正的median。 而是直接去找分别 + k/2的距离后的2个值做比较。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
int total = n1 + n2;
if (total % 2 == 1) {
return getKth(nums1, 0, nums2, 0, total / 2 + 1);
} else {
return (getKth(nums1, 0, nums2, 0, total / 2) +
getKth(nums1, 0, nums2, 0, total / 2 + 1)) /
2.0;
}
}
private:
int getKth(const vector<int>& A, int i, const vector<int>& B, int j,
int k) {
// Always make A the shorter one
if (i >= A.size())
return B[j + k - 1];
if (j >= B.size())
return A[i + k - 1];
if (k == 1)
return min(A[i], B[j]);
int midA = INT_MAX, midB = INT_MAX;
if (i + k / 2 - 1 < A.size())
midA = A[i + k / 2 - 1];
if (j + k / 2 - 1 < B.size())
midB = B[j + k / 2 - 1];
if (midA < midB) {
return getKth(A, i + k / 2, B, j, k - k / 2);
} else {
return getKth(A, i, B, j + k / 2, k - k / 2);
}
}
};
No comments:
Post a Comment