**
Question:
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
**
My code:
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null)
return 0;
if (nums1.length == 0 && nums2.length == 0)
return 0;
int m = nums1.length;
int n = nums2.length;
if (m == 0)
if (n % 2 == 1)
return nums2[n / 2];
else
return ((double)nums2[n / 2] + (double)nums2[n / 2 - 1]) / 2.0;
else if (n == 0)
if (m % 2 == 1)
return nums1[m / 2];
else
return ((double)nums1[m / 2] + (double)nums1[m / 2 - 1]) / 2.0;
int indexOfNums1 = 0;
int indexOfNums2 = 0;
boolean isOutOfRange = false;
int[] mergeArray = new int[m + n];
for (int i = 0; i < m + n; i++) {
if (indexOfNums1 < m && (nums1[indexOfNums1] < nums2[indexOfNums2] || isOutOfRange)) {
mergeArray[i] = nums1[indexOfNums1];
indexOfNums1++;
}
else {
mergeArray[i] = nums2[indexOfNums2];
if (indexOfNums2 < n - 1)
indexOfNums2++;
else
isOutOfRange = true;
}
}
if ((m + n) % 2 == 1)
return mergeArray[(m + n) / 2];
else
return ((double)mergeArray[(m + n) / 2] + (double)mergeArray[(m + n) / 2 - 1]) / 2.0;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {100001};
int[] b = {100000};
System.out.println(test.findMedianSortedArrays(a, b));
}
}
My test result:
這次的難度是hard，但是我一看到就有了思路蛹疯，然后花了十分鐘寫了出來。
這不就是歸并排序（Merge Sort）的簡(jiǎn)單版本么固翰。骂际。冈欢。
給兩個(gè)已排序好的數(shù)列，然后將它們合并太示，獲得一個(gè)新的數(shù)列
來香浩，復(fù)習(xí)下歸并排序。
我自己創(chuàng)造的一個(gè)圖書餐弱。
. . . . . . . . 一個(gè)array囱晴，用歸并排序來處理
. . . . | . . . . 分成兩個(gè)array，分別進(jìn)行歸并排序
. . | . . | . . | . . 對(duì)于每個(gè)子array,再次分成兩個(gè)array驮瞧，分別進(jìn)行歸并排序论笔。
此時(shí)每個(gè)部分只有兩個(gè)數(shù)字了， lo指向第一個(gè)狂魔，頭。hi指向最后一個(gè)理茎，也是第二個(gè)管嬉，尾。
于是進(jìn)行簡(jiǎn)單的排序础倍。完成了胎挎。退回到上步。
. . | . . | . . | . . 此時(shí)的子array都是已經(jīng)排序好了的德迹。于是將 1,2子array歸并揭芍，3,4子array歸并称杨。
. . . . | . . . . 此時(shí)的兩個(gè)子array也是已經(jīng)排序好了的。于是將它們歸并悬而，得到最后的排序結(jié)果锭汛。
. . . . . . . .
然后歸并排序的核心就是這次作業(yè)寫的椰憋。
兩個(gè)array，然后我先創(chuàng)建一個(gè)array長(zhǎng)度是他們的長(zhǎng)度和。
然后通過移動(dòng)指針左电，將兩個(gè)數(shù)組對(duì)應(yīng)位置較小的拷貝進(jìn)入mergeArray页响，然后指針再往前一格闰蚕。這樣连舍，掃描(m + n)次就能完成了。
然后處理一些數(shù)組越界問題盼玄。就差不多潜腻。復(fù)雜度是 N * Log(N)
**
總結(jié)：
歸并排序。
數(shù)組越界融涣。
**
最近兩次作業(yè)都是十幾分鐘寫出來了。剃斧。忽你。是我太強(qiáng)了嗎？
我不覺得筋粗。我覺得是評(píng)測(cè)系統(tǒng)有問題炸渡。這兩道題目正常人應(yīng)該都半小時(shí)內(nèi)就能做出來吧。
最近聽了荔枝FM的一個(gè)廣播买决。額吼畏，首先聲明，我絕對(duì)不是做廣告的人躲舌。
很感動(dòng)没卸。然后那么一句話。
**
其實(shí)我也是一個(gè)普通人啊约计。
**
打到我內(nèi)心了。
小說世界里耕挨， 泰廣尉桩，米可，最后能破鏡重圓赋铝。
現(xiàn)實(shí)世界里沽瘦，會(huì)有這般失而復(fù)得的事嗎？
所以良哲，確定你想要的助隧，然后堅(jiān)持下去。
讀者們肯定看不懂我說的這些話巍实，但你呢棚潦，應(yīng)該看得懂吧膝昆。
我愿意為你改變很多，放棄很多妹窖。
你也愿意為我忍耐很多收叶，擔(dān)心很多。
異地異國(guó)實(shí)在是太難熬谒麦，但熬出頭了呢哆致。
如果因?yàn)槟敲匆患氖拢蹅冏罱K放棄耻蛇。不知道你會(huì)怎么想胞此。
我的話，一定會(huì)有新的女朋友夺蛇，家庭酣胀。
但這份對(duì)你的遺憾，會(huì)陪伴我甚脉，直到進(jìn)入棺材牺氨。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return -1;
}
else if (nums2.length < nums1.length) {
return findMedianSortedArrays(nums2, nums1);
}
else if (nums2.length == 0) {
return -1;
}
int m = nums1.length;
int n = nums2.length;
int half = (m + n + 1) / 2;
int imin = 0;
int imax = m;
while (imin <= imax) {
int i = (imax + imin) / 2;
int j = half - i;
if (i - 1 >= 0 && j < n && nums1[i - 1] > nums2[j]) {
imax = i - 1;
}
else if (j - 1 >= 0 && i < m && nums2[j - 1] > nums1[i]) {
imin = i + 1;
}
else {
int left = 0;
if (i == 0) {
left = nums2[j - 1];
}
else if (j == 0) {
left = nums1[i - 1];
}
else {
left = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2 == 1) {
return left;
}
int right = 0;
if (i == m) {
right = nums2[j];
}
else if (j == n) {
right = nums1[i];
}
else {
right = Math.min(nums1[i], nums2[j]);
}
return (left + right) / 2.0;
}
}
return -1;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums1 = new int[]{1,2};
int[] nums2 = new int[]{3,4,5,6};
double ret = test.findMedianSortedArrays(nums1, nums2);
System.out.println(ret);
}
}
reference：
https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation/2
這道題目實(shí)在是太惡心了猴凹。弄了一個(gè)多小時(shí)精堕。
corner case 太多了蒲障。。庄撮。
看下講解毙籽，思路清晰了很多。但是還是調(diào)了很久很久烙如。
最大的問題是，得把短的作為切割的第一數(shù)組蝇刀，即徘溢， i
因?yàn)槿绻虚L(zhǎng)的，作為i
那么 j很有可能變成負(fù)數(shù)站粟，會(huì)出現(xiàn)錯(cuò)誤曾雕。
如果切短的，就不會(huì)用這個(gè)問題切诀。
還有個(gè)注意的地方就是：
half = (m + n + 1) / 2;
這樣保證趾牧，如果 m + n 是偶數(shù)，
那么左右部分個(gè)數(shù)相等翘单。
如果是奇數(shù)哄芜，那么左邊會(huì)多一個(gè)柬唯。
而且imax = m 而不是 m - 1，真的求中點(diǎn)锄奢。
如果m是奇數(shù)拘央，就是正中點(diǎn)。如果m是偶數(shù)灰伟，是中間兩個(gè)數(shù)右邊那個(gè)。
這些正好都是我們需要的特性栈源。
實(shí)在是太惡心了竖般。
加油！
Anyway, Good luck, Richardo! -- 09/01/2016
