共计 3233 个字符，预计需要花费 9 分钟才能阅读完成。
记录这几天刷题做到的一个数组的算法题的过程：
给定两个大小别离为 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
算法的工夫复杂度应该为 O(log (m+n))。
起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {}剖析
此题目在力扣的难度为艰难，乍一看题目并不是很难，用数组合并的笨办法就能够解决。
真正的难点在于工夫复杂度是 Log 级别
咱们先来看一下不要求的工夫复杂度的状况下如何解决。
奇偶判断
如果总数是奇数，返回两头值，如果总数是偶数，返回两头值和两头值 +1（因为给出的数据结构是数组，所有的下标 -1）
如果不想用 IF 实现判断，也能够应用条件值的判断，如：
return (nums2_length % 2 == 0) ? // 是 0 吗？(nums2[middle - 1] + nums2[middle] ) / 2.0 : // 如果是 0 阐明是偶数，返回两头两个树的平均值
nums2[middle]; // 如果不是 0 阐明是奇数，返回两头的数边界条件
首先思考边界条件，题目的输出可能会呈现一个数组为空的状况，如：
输出：nums1 = [1,3], nums2 = []
输出：nums1 = [], nums2 = [2,3,4]这种状况独自加一个判断，如果有一个数组为空，就间接用下标求出另一个数组的中位数并间接返回，不须要合并数组：
// 长度
int nums1_length = nums1.length;
int nums2_length = nums2.length;
int total_length = nums1_length + nums2_length;
// 如果数组 1 为空，求数组 2 的中位数
if (nums1_length == 0) {
int middle = nums2_length / 2;
return (nums2_length % 2 == 0) ?
(nums2[middle - 1] + nums2[middle] ) / 2.0 :
nums2[middle];
}
// 如果数组 2 为空，求数组 1 的中位数
if (nums2_length == 0) {
int middle = nums1_length / 2;
return (nums1_length % 2 == 0) ?
(nums1[middle - 1] + nums1[middle] ) / 2.0 :
nums1[middle];
} 个别状况
在两个数组都非空的状况下，尝试合并数组，而后取最终数组的中位数
首先定义了三个索引，别离是合并后的索引，nums1 的索引，nums2 的索引，而后创立一个永真循环：
int[] nums = new int[total_length];
// i：合并后的列表的索引，j：nums1 的索引，k：nums2 的索引
int i = 0, j = 0, k = 0;
//
while (true) {}接下来看几种状况：
如果 nums1 的索引等于它的长度，阐明这个数组循环完结了，只把 nums2 拼接到合并后数组的前面即可
if (j == nums1_length && k != nums2_length) {nums[i] = nums2[k];
k++;
i++;
}
else if (j != nums1_length && k == nums2_length) {nums[i] = nums1[j];
j++;
i++;
}如果两个数组的索引都等于他们的长度，阐明循环完结，跳出循环，返回合并后数组的中位数
else if (j == nums1_length && k == nums2_length) {
int middle = total_length / 2;
return (total_length % 2 == 0) ?
(nums[middle - 1] + nums[middle] ) / 2.0 :
nums[middle];
}其余状况就是失常的状况了，因为原有数组是升序，合并后的数组也是升序，也就是插入每次比拟时更小的那个
else {if (nums1[j] > nums2[k]) {nums[i] = nums2[k];
k++;
} else {nums[i] = nums1[j];
j++;
}
i++;
}小结
整个流程就变成了：
①看是否有一个数组是空，如果有，间接返回另一个数组的中位数
②开始循环，每次循环验证是否有数组的索引等于数组长度，
如果一个数组满足，阐明这个数组循环结束，间接把另一个数组的尾部插入到合并后数组的尾部
如果两个数组满足，阐明循环完结，返回合并后数组的中位数
如果没有数组满足，进入③
③失常状况下：比拟两个数，插入更小的数字，进行下一次循环
最初发现这个算法工夫复杂度是 O（m+n），空间复杂度 O（m+n）
残缺代码：
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 长度
int nums1_length = nums1.length;
int nums2_length = nums2.length;
int total_length = nums1_length + nums2_length;
//
if (nums1_length == 0) {
int middle = nums2_length / 2;
return (nums2_length % 2 == 0) ?
(nums2[middle - 1] + nums2[middle] ) / 2.0 :
nums2[middle];
}
if (nums2_length == 0) {
int middle = nums1_length / 2;
return (nums1_length % 2 == 0) ?
(nums1[middle - 1] + nums1[middle] ) / 2.0 :
nums1[middle];
}
// 定义数组
int[] nums = new int[total_length];
// i：合并后的列表的索引，j：nums1 的索引，k：nums2 的索引
int i = 0, j = 0, k = 0;
// 开始循环
while (true) {
// 数组 1 循环完结
if (j == nums1_length && k != nums2_length) {nums[i] = nums2[k];
k++;
i++;
}
// 数组 2 循环完结
else if (j != nums1_length && k == nums2_length) {nums[i] = nums1[j];
j++;
i++;
}
// 整体循环完结
else if (j == nums1_length && k == nums2_length) {
int middle = total_length / 2;
return (total_length % 2 == 0) ?
(nums[middle - 1] + nums[middle] ) / 2.0 :
nums[middle];
}
// 个别状况
else {if (nums1[j] > nums2[k]) {nums[i] = nums2[k];
k++;
} else {nums[i] = nums1[j];
j++;
}
i++;
}
}
return 0;
}
}初步优化
在不扭转整体思路的状况下，优化思路就是
①不循环整个数组，而是索引达到中位数就进行循环，这样循环次数缩小一半，但复杂度仍是 O（m+n）
②不记录所有的合并后果，而是只保留几个固定元素，达到中位数就进行循环，这样空间复杂度能降到 O（1）
但这样还是无奈满足题目要求，所以只能把整个思路都颠覆掉，合并数组的计划在一开始就是不满足要求的。
扭转思路——二分法
这个思路是真正的解法，但目前看起来比拟难
临时附上链接：https://leetcode.cn/problems/…
到笔者汇报的时候还没齐全看懂，前面再补充