题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例：
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
解题思路
将两个有序数组拼凑为一个数组，排序，获取中位数。
伪代码
bubbleSort
{
Sort
}
findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
nums1, nums2 -> buffer;
bubbleSort(buffer, sizeof(buffer));
get median;
}
解答
/* 冒泡排序 */
void bubbleSort(int num[],int nums)
{
int i = 0, j = 0;
/* 对num进行正向排序 */
for(i = 0; i < nums - 1; i++)
{
for(j = i+1; j < nums; j++)
{
if(num[i] > num[j])
{
num[i] = num[i] + num[j];
num[j] = num[i] - num[j];
num[i] = num[i] - num[j];
}
}
}
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i = 0,j = 0;
int nums = 0;
double val = 0.0;
nums = nums1Size + nums2Size;
int buffer[nums];
/* 将nums1拷贝给num */
for(i = 0; i < nums1Size; )
buffer[j++] = nums1[i++];
/* 将nums2拷贝给num */
for(i = 0; i < nums2Size;)
buffer[j++] = nums2[i++];
/* 对num进行归并排序 */
bubbleSort(buffer, nums);
/* 元素个数为偶数 */
if(nums % 2 == 0)
val = (*(buffer + (nums / 2)) + *(buffer + (nums / 2) - 1)) / 2.0;
/* 元素个数为奇数 */
else
val = *(buffer + (nums / 2)) / 1.0;
return val;
}
