题目地址：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
解题思路：方法一：判断中位数位置，同时从两个数组中筛选。(时间复杂度O（m+n）)
方法二：二分查找(时间复杂度O(log(m+n)))
方法一
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { int i, j; //判断总数奇偶 bool check = (nums1Size + nums2Size) & 1; //判断中心位置 int midIndex = check ? (nums1Size + nums2Size) / 2 + 1 : (nums1Size + nums2Size) / 2; double median = 0.0; int index;//当前位置（基于整体） i = j = 0; index = 0; //判断空数组的情况 if (check) { if (!nums1Size) return nums2[midIndex-1]; else if (!nums2Size) return nums1[midIndex-1]; } else { if (!nums1Size) return (nums2[midIndex] + nums2[midIndex - 1]) / 2.0; else if (!nums2Size) return (nums1[midIndex] + nums1[midIndex - 1]) / 2.0; } while (i < nums1Size && j < nums2Size && index < midIndex) { if (nums1[i] < nums2[j]) median = nums1[i++]; else median = nums2[j++]; index++; } while (i < nums1Size && index < midIndex) { median = nums1[i++]; index++; } while (j < nums2Size && index < midIndex) { median = nums2[j++]; index++; } //奇数 if (check) return median * 1.0; else { if (i == nums1Size) return (median + nums2[j]) / 2.0; else if (j == nums2Size) return (median + nums1[i]) / 2.0; else return nums1[i] > nums2[j] ? (median + nums2[j]) / 2.0 : (median + nums1[i]) / 2.0; } }
方法二：因为是两个有序数组，所以求中位数可以转化成寻找两个有序数组中的第k小的数。（题目要求的时间复杂度，具体理解：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/）
int getKNum(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) { int i, j, ii, jj;//i，j表示变化前的下标；ii，jj是变化后的下标（经过剔除操作后） i = j = 0; while (true) { if (i == nums1Size)//第一组数组都被剔除 return nums2[j + k - 1];//在进行一轮剔除操作后，由于第一组数组全部被剔除，所以需要在第二组剔除剩余k-1个数 if (j == nums2Size)//第二组数组都被剔除 return nums1[i + k - 1]; if (k == 1)//说明只剩下一个，判断大小即可,小的那个就是整个数组第k小的数 return nums1[i] < nums2[j] ? nums1[i] : nums2[j]; //可能数组不够k/2-1个数，所以需要判断与数组长度的关系 ii = (i + k / 2 - 1) < (nums1Size - 1) ? (i + k / 2 - 1) : (nums1Size - 1); jj = (j + k / 2 - 1) < (nums2Size - 1) ? (j + k / 2 - 1) : (nums2Size - 1); if (nums1[ii] < nums2[jj]) { k -= ii - i + 1;//第一组数组剔除的个数 i =ii+1; } else { k -= jj - j + 1;//第二组数组剔除的个数 j = jj + 1; } } } double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { bool check = (nums1Size + nums2Size) & 1; if (check) return getKNum(nums1, nums1Size, nums2, nums2Size, (nums1Size + nums2Size) / 2 + 1) / 1.0; else return (getKNum(nums1, nums1Size, nums2, nums2Size, (nums1Size + nums2Size) / 2 + 1) + getKNum(nums1, nums1Size, nums2, nums2Size, (nums1Size + nums2Size) / 2)) / 2.0; }