LeetCode 4. 寻找两个有序数组的中位数

题目

给定两个大小为 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;
}