记录这几天刷题做到的一个数组的算法题的过程：
给定两个大小别离为 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/...
到笔者汇报的时候还没齐全看懂，前面再补充