[数据结构与算法]求中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays

//
// Created by luocx on 2023/6/7.
//

#include <stdio.h>
#include <malloc.h>

// 假设数组不无序，需要增加排序操作，来个冒泡，N 个元素需要N-1次排序才能结束
int *bubSort(int *nums, int numsSize) {
    for (int i = 0; i < numsSize - 1; ++i) {
        for (int x = 0; x < numsSize - 1; x++) {
            if (nums[x + 1] < nums[x]) {
                int tmp = nums[x];
                nums[x] = nums[x + 1];
                nums[x + 1] = tmp;
            }
        }
    }
    return 0;
}

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
    int *nums3 = (int *) malloc(sizeof(int) * (nums1Size + nums2Size));
    double medianNum = 0.0;
    for (int i = 0; i < nums1Size; i++) {
        nums3[i] = nums1[i];
    }

    for (int j = 0; j < nums2Size; j++) {
        nums3[nums1Size + j] = nums2[j];
    }

    bubSort(nums3, nums1Size + nums2Size);
    for (int a = 0; a < (nums1Size + nums2Size); a++) {
        printf("%d\t", nums3[a]);
    }
    if ((nums1Size + nums2Size) % 2 == 1) {
        medianNum = nums3[(int) ((nums1Size + nums2Size + 1) / 2)];
    } else {
        medianNum = (double) (nums3[(nums1Size + nums2Size) / 2] + nums3[(nums1Size + nums2Size - 2) / 2]) / 2;
    }

    return medianNum;
}

int main() {
    int nums2[] = {6, 5, 3, 9, 7};
    int nums1[] = {1, 9, 4};
    double lens1 = findMedianSortedArrays(nums1, 3, nums2, 5);
    printf("\n%f\n", lens1);
};