刷题笔记:力扣第4题-寻找两个正序数组的中位数

1.本题最容易想到的便是使用双指针来遍历两个数组，根据两个数组总的元素个数和的奇偶来进行中位数的计算，但这样做时间复杂度为O(m + n)，不满足题目要求。本题自己没有想出解法，所以将时间复杂度为O(log(min(m + n)))的解法看懂了，在这里做一个解析。

2.题目本质上就是将左右两边切分为相差绝对值不大于1的两组数，就能找到中位数。本题需要一刀将nums1和nums2切分成四部分，并定义当元素个数和为奇数时中位数出现在左边，先计算出一共需要在左边切分出多少个数：

1. int target = (nums1Size + nums2Size + 1) / 2;

在括号内+1可以保证奇数的情况下中位数在左边。

为了避免后面在元素个数、下标等问题上产生歧义，规定本题二分的时候的左右个数代表的是左右元素数，而不是下标，定义左右元素数l和r：

1. int l = 0, r = nums1Size;

然后进入经典的二分循环中，如果nums1左边放了i个元素，那么nums2左边就应该放target – i个元素：

1. int i = (l + r) / 2;
2. int j = target – i;

本题的一个细节点在于边界控制，切分出的四部分元素组（nums1和nums2的左和右）如果有一组元素数为0，就会产生边界问题，此时就需要引入哨兵节点来解决：

1. int maxLeft1 = (i == 0) ? INT_MIN : nums1[i – 1];
2. int minRight1 = (i == nums1Size) ? INT_MAX : nums1[i];
3. int maxLeft2 = (j == 0) ? INT_MIN : nums2[j – 1];
4. int minRight2 = (j == nums2Size) ? INT_MAX : nums2[j];

当左边最大元素均小于等于右边最小元素，则说明找到了正确的切分位置，此时根据元素和的奇偶来返回对应的值即可：

1. if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1){
2. if ((nums1Size + nums2Size) % 2) return fmax(maxLeft1, maxLeft2);
3. else return (fmax(maxLeft1, maxLeft2) + fmin(minRight1, minRight2)) / 2.0;
4. }

若不满足，则根据实际情况来进行边界调整。若maxLeft1 > minRight2则说明nums1拿多了，所以r最多只能取i – 1个；若maxLeft2 > minRight1则说明nums2拿多了，所以l最少需要取i + 1个：

1. else if (maxLeft1 > minRight2){
2. r = i – 1;
3. } else {
4. l = i + 1;
5. }

为了保证时间复杂度最少，应该在元素数较小的数组中进行二分，所以在代码开头进行判断。若nums1元素数不是较小的，则将nums1和num2的参数反转后重新传入函数中进行计算，这样可以保证nums1一定有较小元素数。

1. if (nums1Size > nums2Size) return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);

3.基于以上思想，可写出完整代码如下：

1. // 寻找两个正序数组的中位数，二分法
2. double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
3. // 保证nums1是更短的数组，减少二分次数
4. if (nums1Size > nums2Size) return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
5. // 左半部分一共需要target个元素
6. int target = (nums1Size + nums2Size + 1) / 2;
7. int l = 0, r = nums1Size;
8. while (l <= r){
9. // i：nums1取i个元素放在左边
10. int i = (l + r) / 2;
11. // j：nums2取j个元素放在左边，左右总数凑够target
12. int j = target – i;
13.
14. // 边界处理：i=0代表nums1左边不取元素；i==nums1Size代表nums1全部放到左边
15. int maxLeft1 = (i == 0) ? INT_MIN : nums1[i – 1];
16. int minRight1 = (i == nums1Size) ? INT_MAX : nums1[i];
17. int maxLeft2 = (j == 0) ? INT_MIN : nums2[j – 1];
18. int minRight2 = (j == nums2Size) ? INT_MAX : nums2[j];
19.
20. // 满足分割条件：左边全部 ≤ 右边全部
21. if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1){
22. // 总长度奇数：中位数就是左半部分最大值
23. if ((nums1Size + nums2Size) % 2)
24. return fmax(maxLeft1, maxLeft2);
25. // 总长度偶数：左最大和右最小的平均值
26. else
27. return (fmax(maxLeft1, maxLeft2) + fmin(minRight1, minRight2)) / 2.0;
28. } else if (maxLeft1 > minRight2){
29. // nums1左边拿太多，i要减小
30. r = i – 1;
31. } else {
32. // nums1左边拿太少，i增大
33. l = i + 1;
34. }
35. }
36. return -1;
37. }

该算法时间复杂度为O(log(min(m + n)))，空间复杂度为O(1)，已是最优解。