【打卡算法】4、寻找两个正序数组的中位数算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群&＃xff1a;1040082875

大家好&＃xff0c;我是小魔龙&＃xff0c;Unity3D软件工程师&＃xff0c;VR、AR&＃xff0c;虚拟仿真方向&＃xff0c;不定时更新软件开发技巧&＃xff0c;生活感悟&＃xff0c;觉得有用记得一键三连哦。

一、题目

1、算法题目

“找到两个数组中正序下的中位数。”

题目链接&＃xff1a;
来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;

链接&＃xff1a;https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

2、题目描述

给定两个大小分别为 m 和 n 的正序&＃xff08;从小到大&＃xff09;数组 num1 和 num2 。请你找出并返回这两个正序数组中的 中位数。

比如&＃xff1a;

num1 &＃61; [1,2] , num2 &＃61; [3,4]

输出&＃xff1a;2.50000

合并后数组 &＃61; [1,2,3,4] &＃xff0c;中位数(2&＃43;3)/2&＃61;2.5。

二、解题

1、思路分析

这道题解出来还是很容易的&＃xff0c;难的是对于算法的优化。
首先&＃xff0c;想到的是暴力解法&＃xff0c;将两个数组合并为一个有序数组&＃xff0c;再根据长度决定是取中位数&＃xff0c;还是计算中位数即可。

如果两个数组都是有序的&＃xff0c;也可以在不进行合并数组的情况下进行寻找&＃xff0c;比如说使用两个指针分别指向两个数组的下标0的位置&＃xff0c;每次将指向较小值的指针后移一位&＃xff0c;如果一个指针已经到达数组末尾&＃xff0c;则只需要移动另一个数组的指针&＃xff0c;直到到达中位数的位置。

2、代码实现

使用一个List&＃xff0c;将两个数组都添加到List里面&＃xff0c;然后使用Sort方法进行排序&＃xff0c;根据排序后的List的长度的奇偶&＃xff0c;进而决定是直接返回中位数&＃xff0c;还是计算中位数然后返回。

public class Solution
{public double FindMedianSortedArrays(int[] nums1, int[] nums2) {int m &＃61; nums1.Length;int n &＃61; nums2.Length;int len &＃61; m &＃43; n;var resultIndex &＃61; len / 2;List<int> list &＃61; new List<int>(nums1);list.AddRange(nums2);list.Sort();if (len % 2 &＃61;&＃61; 0){return (list[resultIndex - 1] &＃43; list[resultIndex]) / 2.0;}else{return list[resultIndex];}}
}


执行结果&＃xff1a;

3、时间复杂度

时间复杂度&＃xff1a;O((m&＃43;n)(1&＃43;log(m&＃43;n)))

将两个数组m和n添加到list里面&＃xff0c;复杂度分别是常数级的m&＃43;n&＃xff0c;而Sort方法的复杂度为(m&＃43;n)(log(m&＃43;n)),所以该方法的时间复杂度为O((m&＃43;n)&＃43;(m&＃43;n)log(m&＃43;n)))&＃61;O((m&＃43;n)(1&＃43;log(m&＃43;n)))

空间复杂度&＃xff1a;O(m&＃43;n)

长度为数组m&＃43;n

三、总结

这个算法还不是最优解&＃xff0c;时间复杂度和空间复杂度都比较高。

可以不进行数组合并&＃xff0c;分别查找中位数&＃xff0c;然后再使用二分查找。

这个以后学习了再填坑吧。