Median of Two Sorted Arrays
題目:
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)).
You may assume nums1 and nums2 cannot be both empty.
描述：兩個(gè)已經(jīng)排序好的數(shù)組新博，數(shù)組不是空蜘腌，求中位數(shù)。要求算法的時(shí)間復(fù)雜度是O(long(m+n))。
分析:
1、如果不看時(shí)間復(fù)雜度的話，可以使用暴力方法實(shí)現(xiàn)：把兩個(gè)數(shù)組拼接伸蚯，然后重新排序，尋找中位數(shù)简烤，較為簡(jiǎn)單剂邮，使用Java實(shí)現(xiàn)。
2横侦、要是考慮復(fù)雜度的話挥萌，較為困難绰姻，后面會(huì)用C語(yǔ)言具體分析。
1引瀑、Java實(shí)現(xiàn)
內(nèi)容簡(jiǎn)單龙宏，這里不做解釋。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double median = 0.0f;
int m = nums1.length;
int n = nums2.length;
int[] newNums = Arrays.copyOf(nums1, nums1.length + nums2.length);
System.arraycopy(nums2, 0, newNums, nums1.length, nums2.length);
Arrays.sort(newNums);
if ((m + n) % 2 == 0) {
median = (newNums[(m + n) / 2] + newNums[(m + n) / 2 - 1]) / 2.0;
} else {
median = newNums[(m + n) / 2];
}
return median;
}
運(yùn)行時(shí)間：
時(shí)間復(fù)雜度：主要是Arrays.sort()使用的快排伤疙，時(shí)間復(fù)雜度為O( (n+m)*log(n+m) )
空間復(fù)雜度：O(n+m)
2银酗、 C語(yǔ)言實(shí)現(xiàn)(1)
新建一個(gè)長(zhǎng)度為 (m+n)/2 +1 的數(shù)組newnums，i,j為先指向數(shù)組nums1 和mums2的第0個(gè)元素,通過i,j的移動(dòng)把兩個(gè)源數(shù)組的按照升序復(fù)制到新數(shù)組newnums中徒像。
1. 處理源數(shù)組是空的情況黍特，一個(gè)如果是空，另一個(gè)直接復(fù)制數(shù)組到
newnums中锯蛀。2. 兩個(gè)都不為空灭衷，開始循環(huán)，循環(huán)次數(shù)為length/2+1(總長(zhǎng)度一半+1)
3. 控制移動(dòng)邊界
i>=num1Size時(shí)旁涤，nums1到最后一個(gè)元素翔曲，從nums2賦值，j>=num2Size時(shí)劈愚，nums2到最后一個(gè)元素瞳遍，從nums1賦值。
判斷nums1[i] < nums2[j],每次都把較小的元素賦值到新數(shù)組中菌羽。4.分偶數(shù)和奇數(shù)判斷中位數(shù)情況掠械。
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
int length = nums1Size + nums2Size;
int *newnums = (int *) malloc(sizeof(int) * (length / 2 + 1));
int index = 0, i = 0, j = 0;
double median;
if (nums1Size == 0) {
newnums = nums2;
} else if (nums2Size == 0) {
newnums = nums1;
} else {
while (index <= length / 2) {
if (i >= nums1Size) {
newnums[index] = nums2[j];
j++;
} else if (j >= nums2Size) {
newnums[index] = nums1[i];
i++;
} else {
if (nums1[i] < nums2[j]) {
newnums[index] = nums1[i];
i++;
} else {
newnums[index] = nums2[j];
j++;
}
}
index++;
}
}
if (length % 2 == 0) {
median = (newnums[length / 2 - 1] + newnums[length / 2]) / 2.0;
} else {
median = newnums[length / 2];
}
return median;
}
運(yùn)行時(shí)間：
時(shí)間復(fù)雜度：O((n+m)/2+1) = O(n)
空間復(fù)雜度：O((n+m)/2+1) = O(n)
3、C語(yǔ)言實(shí)現(xiàn)(2)
中位數(shù)的定義是把一個(gè)集合分為左右長(zhǎng)度相等的兩個(gè)子集合注祖，所以我們?nèi)绻ＷC兩個(gè)數(shù)組的猾蒂，左半部分的長(zhǎng)度=右半邊分長(zhǎng)度，就可以找出中位數(shù)是晨。
這時(shí)候要保證:
len(left_part) = len(right_part)
max(left_part) <=min(right_part)
令
len(left_part) = i
len(right_part)) = j
i = m - i
j = n - j
因此我們需要確保
- i + j = m - i +n - j (or i + j = m - i + n - j + 1)
if m<=n 我們需要設(shè)置 i ~(0,m) 肚菠， j = (m + n + 1)/2 - i- nums2[j?1]≤nums1[i] 和 nums1[i?1]≤nums2[j]
我們需要先確保m<=n，如果m>n時(shí)罩缴，j可能會(huì)小于 0蚊逢，然后使用二分法查詢數(shù)組，處理好四種邊界問 題i = 0 靴庆，j = 0 时捌，i = m 或 j = n的情況，具體細(xì)節(jié)看代碼炉抒。
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
int m = nums1Size;
int n = nums2Size;
if (m > n) { // to ensure m<=n
int *temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && nums2[j - 1] > nums1[i]) {
iMin = i + 1; // i is too small
} else if (i > iMin && nums1[i - 1] > nums2[j]) {
iMax = i - 1; // i is too big
} else { // i is perfect
int maxLeft = 0;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
}
if ((m + n) % 2 == 1) {
return maxLeft;
}
int minRight = 0;
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = nums2[j] > nums1[i] ? nums1[i] : nums2[j];
}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
耗時(shí)如圖：
還是比較不錯(cuò)的奢讨。
時(shí)間復(fù)雜度：O(log(min(m,n))).
空間復(fù)雜度：O(1)
