时间轴

2025-12-04

init

题目：

P4 寻找两个正序数组的中位数

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-interview-150

O((m+n)/2)解法，合并数组，不过还能优化（当一个数组已经为空时，可以直接计算中位数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <vector>
using std::vector;

class Solution {
    public:
        double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
        {
                int m = nums1.size(), n = nums2.size();
                int last_num;

                int mi = 0, ni = 0;
                int index = 0;
                int total = m + n;
                double res = 0;

                while (mi < m || ni < n) {
                        if (mi < m && ni < n) {
                                if (nums1[mi] < nums2[ni]) {
                                        last_num = nums1[mi++];

                                } else {
                                        last_num = nums2[ni++];
                                }
                        } else if (mi >= m && ni < n) {
                                last_num = nums2[ni++];

                        } else if (mi < m && ni >= n) {
                                last_num = nums1[mi++];
                        }

                        
                        if (total % 2 == 0) {
                                if(index == total / 2 - 1){
                                        res += last_num;
                                }else if(index == total / 2){
                                        res += last_num;
                                        res = (double) res/2;
                                        break;
                                }
                        } else {
                                if (index == total / 2) {
                                        res = last_num;
                                        break;
                                }
                        }
                        index++;
                }
                return res;
        }
};

二分法：（没看懂 TODO）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <vector>
#include <algorithm>
#include <climits>
using std::vector;
using std::max;
using std::min;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.size() > nums2.size())
                return findMedianSortedArrays(nums2, nums1);

        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        int totalLeft = (m + n + 1) / 2;  // 左半部分元素个数

        while (left <= right) {
            int i = left + (right - left) / 2;  // nums1 分割位置
            int j = totalLeft - i;              // nums2 分割位置

            int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];
            int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
            int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];
            int nums2RightMin = (j == n) ? INT_MAX : nums2[j];

            if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
                // 找到正确分割
                if ((m + n) % 2 == 1) {
                    return (double)max(nums1LeftMax, nums2LeftMax);
                } else {
                    return (double)(max(nums1LeftMax, nums2LeftMax) + 
                                    min(nums1RightMin, nums2RightMin)) / 2;
                }
            } else if (nums1LeftMax > nums2RightMin) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }

        // 理论上不会到这里
        return 0.0;
    }
};