Leetcode 寻找两个有序数组的中位数

2021-02-06 16:18

阅读：712

标签：logs 组合 ted 个数 ble 复杂一个 median class

2020-04-26

原题链接

思路

题意就是寻找两个有序数组的中位数。第一反应可能会先把两个数组合并然后再找中位数，但是显然我们没有必要把合并后的数组存起来，只要依次搜索，得到最中间的一个或两个就可。美中不足的是它的时间复杂度为 O(m + n) 。

为了达到题目中时间复杂度为 O(log(m + n)) 的要求，我们可以使用二分（其实也是看了题解后 ohhhhhhh ）。前面我们是一个一个剔除，现在我们可以一次剔除 (m + n) / 4 个。直接比较 nums1[(m+n)/4] 和 nums2[(m+n)/4] ，若 nums1[(m+n)/4] 小，则它和它之前的部分就可以被直接剔除，因为他们一定是在中位数之前（我也想过是否也可以把 nums2[(m+n)/4] 之前的也去掉呢，答案是不可以）。以这个思路反复直到得到 (m + n) / 2 和 (m + n) / 2 + 1 位的两个数。这个方法的边界判断烦得不行，更有趣的是要注意 [] [1] 类似的各种极端情况。

顺便吐嘈一句这个垃圾网站 coding 体验极差 hhh

代码

O(m + n)：

/*
 *lang C++
 *user weilinfox
 */
class Solution {
public:
    static double findMedianSortedArrays(vector& nums1, vector& nums2) {
        long long a = nums1.size(), b = nums2.size();
        int t, tp;
        for (long long i = 0, j = 0; i + j + 1  nums2[j]) {
                    t = nums2[j];
                    j++;
                } else
                    i++;
            } else if (i

by SDUST weilinfox
本文链接 https://www.cnblogs.com/weilinfox/p/12781374.html

Leetcode 寻找两个有序数组的中位数

标签：logs 组合 ted 个数 ble 复杂一个 median class

原文地址：https://www.cnblogs.com/weilinfox/p/12781374.html

上一篇：Spring Boot 自定义kafka 消费者配置 ContainerFactory最佳实践

下一篇：js数组方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Leetcode 寻找两个有序数组的中位数
文章链接：http://soscw.com/index.php/essay/51805.html

亲，登录后才可以留言！

Leetcode 寻找两个有序数组的中位数

评论

热门文章

推荐文章

最新文章

置顶文章