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

Posted on | In |
Words count in article: 216 | Reading time ≈ 1

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

分析：

1
归并思想

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        int i = 0, j = 0;
        vector<int> t(n + m);
        int k = 0;
        while (i < n && j < m) {
            if (nums1[i] <= nums2[j]) t[k ++] = nums1[i ++];
            else t[k ++] = nums2[j ++];
        }
       
        while (i < n) t[k ++] = nums1[i ++];
        while (j < m) t[k ++] = nums2[j ++];
        if ((n + m) % 2 == 1) return double(t[(n + m) / 2]);
        return double(t[(n + m) / 2] + t[(n + m) / 2 - 1]) /  2.;
    }
};

[原题链接](5. 最长回文子串 - 力扣（Leetcode）)

0%