leetcode-4. 尋找兩個正序陣列的中位數，
給定兩個大小為 m 和 n 的正序（從小到大）陣列 nums1 和 nums2，
請你找出這兩個正序陣列的中位數，并且要求演算法的時間復雜度為 O(log(m + n))，
你可以假設 nums1 和 nums2 不會同時為空，
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problemset/all/
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
double answer = 0.0;
int i1 = 0, i2 = 0, ti = 0, *tempArray = NULL;
tempArray = malloc( sizeof(*tempArray) * (nums1Size + nums2Size) );
while( i1 < nums1Size && i2 < nums2Size ) {
tempArray[ti++] = nums1[i1] <= nums2[i2] ? nums1[i1++] : nums2[i2++];
}
while( i1 < nums1Size ) {
tempArray[ti++] = nums1[i1++];
}
while( i2 < nums2Size ) {
tempArray[ti++] = nums2[i2++];
}
answer = (ti & 1) ? tempArray[ti / 2] * 2 : tempArray[ti / 2] + tempArray[ti / 2 - 1];
free( tempArray );
return answer / 2.0;
}
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
int lasttime = 0, current = 0, len = nums1Size + nums2Size;
int half = len / 2;
for( int i1 = 0, i2 = 0, i = 0; i <= half; ++i ) {
lasttime = current; // 記錄中位數上一次的位置的值.
if( i2 >= nums2Size || (i1 < nums1Size && nums1[i1] <= nums2[i2]) ) {
current = nums1[i1++];
} else if( i2 < nums2Size ) {
current = nums2[i2++];
}
}
return len & 1 ? current : (lasttime + current) / 2.0;
}
由于數列是有序的,其實完全可以一半一半的排除,
假設要找第 k 小的元素, 遍歷程序中每次排除掉 k/2 個元素.
參考： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
#define MIN( a, b ) ((a) <= (b) ? (a) : (b))
static int recursion( int a[], int aSize, int b[], int bSize, int k ) {
int kc2 = k / 2;
int ai = MIN( aSize, kc2 ) - 1, bi = MIN( bSize, kc2 ) - 1;
if( aSize < 1 || bSize < 1 ) {
return aSize < 1 ? b[k - 1] : a[k - 1];
}
if( k < 2 ) {
return MIN( a[0], b[0] );
}
if( a[ai] <= b[bi] ) {
return recursion( a + MIN( aSize, ai + 1 ), aSize - (ai + 1), b, bSize, k - (ai + 1) );
}
return recursion( a, aSize, b + MIN( bSize, bi + 1 ), bSize - (bi + 1), k - (bi + 1) );
}
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
int len = nums1Size + nums2Size;
double answer = 0.0;
// 假設陣列共有7個元素, 則:
// 中位數 = (第4個元素 + 第4個元素) / 2.0.
// 中位數 = (第(8/2)個元素 + 第(9/2)個元素) / 2.0.
// 假設陣列共有8個元素, 則:
// 中位數 = (第4個元素 + 第5個元素) / 2.0.
// 中位數 = (第(9/2)個元素 + 第(10/2)個元素) / 2.0.
// 陣列的元素數量不管是奇數還是偶數,
// 中位數都為 (第((len+1)/2)個元素 + 第((len+2)/2)個元素) / 2.0.
answer += recursion( nums1, nums1Size, nums2, nums2Size, (len + 1) / 2 );
answer += recursion( nums1, nums1Size, nums2, nums2Size, (len + 2) / 2 );
return answer / 2.0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30685.html
標籤：C
上一篇：C 實戰練習題目11
下一篇：解密C語言編譯背后的程序