Leetcode 4.寻找两个正序数组的中位数

type

Post

status

Published

date

Jan 15, 2024

slug

leetcode-4

summary

Problem: 4. 寻找两个正序数组的中位数

思路

💡

直接合并数组再求解，时间复杂为。但是由于数组是有序的，所以有一些数是不必访问的。比如：和,可以知道中位数是5，比中位数大的数有4个。如果知道比4大的数有5个，那么说明4不是中位数，且比4小的数也不可能是中位数。

解题方法

💡

如果和的总长度为，是两个数组的中位数。

如果是奇数：一定是两个数组中的某个数，且总共有个数比大。

如果是偶数：一定是由两个数组中的某两个数取平均得来，对于，总共有个数比大。对于，总共有个数比大。

💡

无论是奇是偶，只要解决一个关键问题即可：找到。是两个数组中的某个数，且总共有个数比大。

首先，假设这个数存在于中。在中取一个数，中有个数比它大，再运用二分找到中有多少个数比它大。如果总个数，则跳出循环。否则根据比它大的数的个数，决定下一轮在的左半部分找还是右半部分找。

如果在中没找到，那么再在中用相同办法找。

💡

需要注意的是，当数组里有相等的数时，就不是直接判断总个数,而是判断它是否满足一个区间。

复杂度

时间复杂度:

在中取了轮数，对于每一轮，在中二分找到第一个比它大的数。所以总的复杂度为

空间复杂度:

Code


#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
class Solution {
public:
// 在nums1中找到一个数nums1[x],使得nums1和nums2中所有比他>的数的个数为bound
int find(vector<int>& nums1, vector<int>& nums2, int n1, int n2,
int bound) {    
int ans = -1;
    int l = 0, r = n1;
    while (l < r) {

        int mid = (l + r) >> 1;
        int x = nums1[mid];

        int i2 = upper_bound(nums2.begin(), nums2.end(), x) -
                 nums2.begin(); // 第一个>x的数的下标
        int i1 = lower_bound(nums2.begin(), nums2.end(), x) -
                 nums2.begin(); // 第一个>=x的数的下标
        int cnt = n1 - mid - 1; // 比x大的数的个数

        int j1 = n2 - i2 + cnt, j2 = n2 - i1 + cnt;

        if (j1 <= bound && j2 >= bound) {
            ans = mid;
            break;
        }
        if (j1 > bound) {
            l = mid + 1;
        }
        if (j2 < bound) {
            r = mid;
        }
    }
    return ans;
}
int cal(vector<int>& nums1, vector<int>& nums2, int n1, int n2, int bound) {
    int ans;
    int t = find(nums1, nums2, n1, n2, bound);

    if (t == -1) {
        t = find(nums2, nums1, n2, n1, bound);

        ans = nums2[t];
    } else {
        ans = nums1[t];
    }
    return ans;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size(), n2 = nums2.size();
    double ans;
    if ((n1 + n2) % 2) {
        ans = cal(nums1, nums2, n1, n2, (n1 + n2) / 2);
    } else {
        int t1 = cal(nums1, nums2, n1, n2, (n1 + n2) / 2);
        int t2 = cal(nums1, nums2, n1, n2, (n1 + n2) / 2 - 1);
        ans = (t1 + t2) * 1.0 / 2;
    }
    return ans;
}};