算法 职场和发展 《三战Leetcode》寻找有序数组的中位数，dubbo工作原理面试题

2、空间复杂度推导 3、执行结果 4、小结 解法三、二分查找法

1、求解第k小数的思路 2、图解步骤讲解 3、代码讲解 4、执行结果 5、时间复杂度推导 6、空间复杂度推导 7、小结 算法思想在实际的应用 写在最后

一、前言

一、前言

大家好，又到了三分钟算法修行时间，之前挑选的算法都是中低难度的，这次找个难度较高的，看看会遇到啥问题。至于难到啥程度，来看看Leetcode下解题的网友评论。

本篇文章大纲：

二、 题目

二、 题目

名称：寻找两个正序数组的中位数

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

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]

输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]

输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []

输出：2.00000

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

进阶要求：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗(注意这个要求，这个要求才是解决这道题目的关键)

三、题目解析

三、题目解析

这道题目很简单，就是从两个有序的数组中查询到它们的中文数，难点在于如何设计一个事件复杂度为O(log(m+n))的算法。 下面抽取题目关键信息来解读题目：

中位数：指顺序排序一组数据中居于中间位置的数值。 它分为两种情况，一是当数组长度为奇数时，正中间的数为中位数，二是当数组长度为偶数时，通常是将最中间的两个数相加取平均值作 为中位数，具体看下图：

解法一：暴力破解

相信很多小伙伴一看到题目，脑海中就已经有了这种解题的思路：将两个数组合并起来 ，然后重新排序，再根据奇偶情况获取合并后的新数组的中位数。

1、解题代码：

/**

方式一：时间复杂度和空间复杂度都为O(m+n) @param nums1 @param nums2 @return

*/

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

int numLength = nums1.length + nums2.length;

// 定义合并后的集合

List list = new ArrayList();

// 使用for循环将元素添加到新的数组(方式一)

//for (int i : nums1) {

// list.add(i);

//}

//for (int i : nums2) {

// list.add(i);

//}

// 使用lambda表达式将数组合并到集合中(方式二)

list.addAll(Arrays.stream(nums1).boxed().collect(Collectors.toList()));

list.addAll(Arrays.stream(nums2).boxed().collect(Collectors.toList()));

// 使用结合工具类的排序方式对存放了两个数组的集合进行排序(sort底层的排序方式是：)

Collections.sort(list);

int middle = list.size() / 2;

// 两数组元素之和为偶数

if (numLength % 2 == 0) {

int leftMiddle = middle - 1;

double middleValue = (Double.valueOf(list.get(leftMiddle)) + Double.valueOf(list.get(middle))) / 2;

return middleValue;

} else {

return Double.valueOf(list.get(middle));

}

}

2、时间复杂度推导：

通过上面的代码，我们会发现随着输入规模的增大(即数组元素增多)，程序需要花费执行时间处理的语句主要是在将[两个数组元素放入新的集合]以及对这个[新的集合进行排序]的过程。

将两个数组元素合并到一个数组执行函数可以使用函数：f(x)=m + n(m,n分别为两个数组的长度)表示，根据大O记法的推导可以得到时间复杂度为：O(m + n)

对新数组排序的Collections.sort()方法的最坏情况下时间复杂度为：O(n * log(n))。

因此，使用暴力破解的方式总的时间复杂度为：O(m+n) + O(n * log(n))，这个复杂度如果当数组长度变长后，效率是会比较低的，不推荐使用。

3、空间复杂度推导：

因为每次合并都需要申请一个新的集合来存放两个数组的元素，所以需要申请空间的函数可以表示为：f(x) = m + n，根据大O记法标准推导，可以得到空间复杂度为：O(m+ n)。

4、执行结果：

解法二、双指针法

暴力破解法，当输入规模大的时候，效率极低，且没有满足题目的进阶要求，能否对时间复杂度和空间复杂度进一步优化呢？

答案是可以的。我们的目的是查询两个有序数组的中位数，在暴力破解中我们是通过申请新的数组集合来存放两个数组的值然后进行排序，最终得出结果，这一步是否真的需要呢？

答案是不需要，我们目的是查询中位数，中位数无非根据数组长度有奇偶两种情况，我们可以使用两个指针来指向对应的元素即可，这样我们就可以省略[申请新的数组空间]和对[新数组重新排序]的两个步骤，从而优化了时间复杂度和空间复杂度，下面来看看具体的代码。

public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {

int num1Length = nums1.length;

int num2Length = nums2.length;

int sumLength = num1Length + num2Length;

// 第一个中位数指针

int preItem = 0;

// 第二个中位数指针(如果两个数组总长度为奇数，则直接返回该值即可)

int curItem = 0;

// 遍历的数组1的元素下标

int num1Index = 0;

// 遍历的数组2的元素下标

int num2Index = 0;

// 需要遍历的次数(查询中位数，并不需要将两个数组元素都遍历完)

int foreachTime = sumLength / 2;

for (int i = 0; i <= foreachTime; i++) {

// 保证preItem总是在curItem前面

preItem = curItem;

// num2Index >= num2Length需要放在nums1[num1Index] < nums2[num2Index]前面，否则会出现下标越界

// nums1[num1Index] < nums2[num2Index]的目的就是为了按照模拟从小到大的顺序循环两个数组的元素

if (num1Index < num1Length && (num2Index >= num2Length || nums1[num1Index] < nums2[num2Index])) {

curItem = nums1[num1Index++];

} else {

curItem = nums2[num2Index++];

}

}

// 如果是偶数，则取中间两个元素的平均值

if (sumLength % 2 == 0) {

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Java）

最后

做任何事情都要用心，要非常关注细节。看起来不起眼的、繁琐的工作做透了会有意想不到的价值。 当然要想成为一个技术大牛也需要一定的思想格局，思想决定未来你要往哪个方向去走, 建议多看一些人生规划方面的书籍,多学习名人的思想格局，未来你的路会走的更远。

更多的技术点思维导图我已经做了一个整理，涵盖了当下互联网最流行99%的技术点，在这里我将这份导图分享出来，以及为金九银十准备的一整套面试体系，上到集合，下到分布式微服务

、学习笔记、源码讲义、实战项目、讲解视频**

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Java） [外链图片转存中…(img-K8vX8c6k-1711089180977)]

最后

做任何事情都要用心，要非常关注细节。看起来不起眼的、繁琐的工作做透了会有意想不到的价值。 当然要想成为一个技术大牛也需要一定的思想格局，思想决定未来你要往哪个方向去走, 建议多看一些人生规划方面的书籍,多学习名人的思想格局，未来你的路会走的更远。

更多的技术点思维导图我已经做了一个整理，涵盖了当下互联网最流行99%的技术点，在这里我将这份导图分享出来，以及为金九银十准备的一整套面试体系，上到集合，下到分布式微服务

[外链图片转存中…(img-UCi8tCET-1711089180977)]

[外链图片转存中…(img-CQjU19pS-1711089180978)]

[外链图片转存中…(img-1rslaLGi-1711089180978)]

[外链图片转存中…(img-jKPZc0q7-1711089180979)]

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录

好文推荐

 您阅读本篇文章共花了： 

大家都在找：

leetcode：leetcode官网下载

算法：算法具有传递性特征对吗

职场和发展：给建筑工程管理新人职场发展的规划与忠告上