题目描述

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解答思路

我的想法是先归并排序再直接返回下标中位数
代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {int i=0,j=0,k=0;int c[nums1Size+nums2Size];while(i<nums1Size&&j<nums2Size){if(nums1[i]<nums2[j])c[k++]=nums1[i++];elsec[k++]=nums2[j++];}while(i<nums1Size)c[k++]=nums1[i++];while(j<nums2Size)c[k++]=nums2[j++];if((nums1Size+nums2Size)%2==1)return c[(nums1Size+nums2Size)/2];elsereturn (c[(nums1Size+nums2Size)/2-1]+c[(nums1Size+nums2Size)/2])/2.0;
}

结果

复杂度分析
时间复杂度：O(m+n）
空间复杂度:O(n+m)

解法二，二分查找法(最优解)

二分查找的算法模板from算法模板

bool check(int x){ /* ... */}//检查x是否满足某种性质//区间[l,r]被划分成[l,mid] 和 [mid+1,r]时使用；
int bsearch_1(int l,int r)
{while(l<r){int mid = l+r >>1;if(check(mid)) r=mid;else l = mid + 1;}return l;
}
//区间[l,r]被划分成[l,mid-1] 和 [mid,r]时使用：
int bsearch_2(int l,int r)
{while(l<r){int mid = l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}return l;
}

既然题目要求对数级别的时间复杂度，我们必须考虑使用二分查找。这里的难点在于，我们不是在一个简单的数组上进行二分，而是在一个“虚拟”的合并数组上进行。

核心思想：转化问题
寻找中位数，本质上是在寻找一个“分割点”，这个分割点能将一个集合分成左右两个部分，且左边部分的所有元素都小于等于右边部分的所有元素。

对于这道题，我们要在 nums1 和 nums2 中找到两个分割点，将两个数组都分成左右两部分。这两个分割点需要满足以下两个条件：
长度条件：左半部分所有元素的个数之和 等于 右半部分所有元素的个数之和（或多一个，当总数为奇数时）。
大小条件：左半部分所有元素的最大值 小于等于 右半部分所有元素的最小值。
只要我们找到了满足这两个条件的分割点，中位数就自然而然地由分割点周围的元素决定了

具体步骤：
为了简化，我们假设 nums1 是长度较短的那个数组（如果不是，可以交换它们）。

• 我们对较短的数组 nums1 进行二分查找。我们要查找的不是一个值，而是一个合适的分割线索引 i。这个 i 将 nums1 分成 nums1[0…i-1]（左半部分）和 nums1[i…m-1]（右半部分）。

• 设总长度的一半为 halfLen = (m + n + 1) / 2。（这里 +1 是一个小技巧，可以同时处理奇偶情况）。

• 一旦 nums1 的分割线 i 确定了，nums2 的分割线 j 也随之确定，必须满足 i + j = halfLen，所以 j = halfLen - i。j 将 nums2 分成 nums2[0…j-1] 和 nums2[j…n-1]。

• 现在我们有了四个关键的边界值：
  nums1 左半部分的最大值：nums1[i-1] (设为 L1)
  nums1 右半部分的最小值：nums1[i] (设为 R1)
  nums2 左半部分的最大值：nums2[j-1] (设为 L2)
  nums2 右半部分的最小值：nums2[j] (设为 R2)

• 接下来，我们检查“大小条件”是否满足。正确的分割线必须满足：L1 <= R2 并且 L2 <= R1。
  如果 L1 > R2：说明 nums1 的分割线 i 太靠右了，nums1 左边的数太大了。我们需要将 i 向左移动。在二分查找中，这意味着要缩小查找区间的右边界 (high = i - 1)。
  如果 L2 > R1：说明 nums1 的分割线 i 太靠左了，nums1 右边的数太小了（等价于 nums2 左边的数太大了）。我们需要将 i 向右移动。在二分查找中，这意味着要扩大查找区间的左边界 (low = i + 1)。
  如果同时满足 L1 <= R2 和 L2 <= R1：恭喜，我们找到了完美的分割线！现在可以计算中位数了：
  如果总长度 (m+n) 是奇数：中位数就是两个左半部分中的最大值，即 max(L1, L2)。
  如果总长度 (m+n) 是偶数：中位数是左半部分最大值和右半部分最小值的平均值，即 (max(L1, L2) + min(R1, R2)) / 2.0。

• 处理边界：当 i 或 j 为 0 或数组长度时，其左边或右边可能没有元素。这时我们可以把 L1, L2 视为负无穷大，把 R1, R2 视为正无穷大，这样大小比较的逻辑依然成立。

代码实现：
不太会写，学习一下g老师的代码

#include <stdio.h>
#include <limits.h> // 用于 INT_MIN 和 INT_MAX// 一个简单的宏来获取最大值和最小值，比引入 math.h 更轻量
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {// 确保 nums1 是较短的数组，这样可以减少二分查找的次数if (nums1Size > nums2Size) {return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);}int m = nums1Size;int n = nums2Size;int low = 0, high = m;// 在较短的数组 nums1 上进行二分查找while (low <= high) {// partition1 是 nums1 的分割点int partition1 = low + (high - low) / 2;// partition2 是 nums2 的分割点，根据总长度的一半来计算int partition2 = (m + n + 1) / 2 - partition1;// 获取分割线左侧的最大值// 如果 partition1 为 0，说明 nums1 的左半部分为空，取负无穷int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];// 如果 partition2 为 0，说明 nums2 的左半部分为空，取负无穷int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];// 获取分割线右侧的最小值// 如果 partition1 等于 m，说明 nums1 的右半部分为空，取正无穷int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];// 如果 partition2 等于 n，说明 nums2 的右半部分为空，取正无穷int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];// 检查是否找到了完美的分割线if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {// 如果总元素个数是偶数if ((m + n) % 2 == 0) {return (MAX(maxLeft1, maxLeft2) + MIN(minRight1, minRight2)) / 2.0;} else { // 如果总元素个数是奇数return (double)MAX(maxLeft1, maxLeft2);}} // 如果 nums1 左边的最大值大于了 nums2 右边的最小值// 说明 partition1 太大了，需要向左移动else if (maxLeft1 > minRight2) {high = partition1 - 1;} // 否则说明 partition1 太小了，需要向右移动else {low = partition1 + 1;}}// 如果程序运行到这里，说明输入数组不是有序的，按题目要求不会发生// 在实际工程中，这里应该抛出异常return -1.0; 
}// ------ 主函数用于测试 ------
int main() {// 测试用例 1: 奇数总长int nums1[] = {1, 3};int nums2[] = {2};double median1 = findMedianSortedArrays(nums1, 2, nums2, 1);printf("Test Case 1: Median is %f\n", median1); // 应该输出 2.0// 测试用例 2: 偶数总长int nums3[] = {1, 2};int nums4[] = {3, 4};double median2 = findMedianSortedArrays(nums3, 2, nums4, 2);printf("Test Case 2: Median is %f\n", median2); // 应该输出 2.5return 0;
}

运行结果：

复杂度分析：
时间复杂度：O(log(min(m,n)))
空间复杂度：O(1)
ok see you next time~