继续一天一个算法题，额….这个要求真的有点高 o(╥﹏╥)o ，今天这个算法题在LeetCode上是一个困难级别的题，我在看完这个题后基本上有了个大概的思路，然而理想很丰满，现实很骨感，用代码实现算法却用了一天多。这里记录一下我的解题思路
寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5备注：
中位数：中位数的概念是初中的内容，简单来说，就是一个有序数组的中间那个数（如果数组长度是奇数，中位数是中间那个数；如果长度是偶数，中位数是中间两个数的平均数）有序数组：题干中有一点没讲清楚，就是只说了是两个有序数组，而没有说是两个升序数组，或者是两个降序数组，又或者一个升序一个降序。但我提交通过的代码，默认是处理两个数组是升序的，所以LeetCode这道题默认是针对两个升序数组的，我本地又测了一下两个降序和一个升序一个降序的情况，发现不能得到正确结果（后来我想了想，其实如果代码能正确得到两个升序数组的中位数，那么两个降序和一个升序一个降序的情况，只要稍加处理一下就行了，哈哈）
解题思路
所谓一千个人眼中有一千个哈姆雷特，不同的人对同一个题目有不同的算法思路，这里只记录我个人的解题思路。这道题要求算法复杂度是O(log(m + n))，这意味着只能遍历一次数组才能满足这个要求。而这道题最有用的价值就是两个数组已经是有序数组，要很好的利用这个特点。而不是首先想着把两个数组合成一个数组，然后再排好序，再求中位数。因此看完这道题时，我的脑海中有一个画面，想像有一个小人从数组的左边走到右边，他每次只能走一个数字，而且每走一步只能选择这两个数组中比较小的数走，然后走第二大的数，然后走第三大的数，依次这样走下去。当小人走的步数是两个数组长度的一半数时，他脚下的数字就是中位数了。这个思路的算法复杂度很小，没有任何多余的算法步骤，虽然思路是这样想的，但实际写代码时却总是不自觉得去遍历两个数组（因为发现如果不遍历，该怎么往右走呢），以至于花费了大半天时间还是得不到正确的结果，后来我再去仔细想了想这个思路过程，发现重要的不是遍历，而得需要知道下一步该怎么走（即是应该继续在这个数组上右移一步，还是应该跳到另一个数组）。也就是说我每走一步都需要规划下一步该怎么走，于是我写了一个死循环，然后每次循环时去规划下一次循环应走的代码逻辑（即 if...else...），然后再适当的时候跳出循环即可（即 if...break）。按这个思路这道题需要解决的问题点有三个：
动态规划：每右移一步时，要分别获取数组1和数组2的下一个元素，比较大小，然后选择较小的数组继续右移临界判断：存在一种情况，就是数组1的值比数组2的值全都小时，数组1跑完后，到数组2时就不需要再获取数组1的元素做动态规划了长度判断：当两数组长度和为奇数时比较好处理，当长度和为偶数时，跑到中间后，需把中间的数值先记下来，然后继续右移一位，这时再和刚刚记下的数值求和算中位数
代码实现
Java版本
public static double getMiddleByTwoNumbers(int[] nums1 ,int[] nums2){
int value1=0,value2=0;
// 声明两个游标,两个数组谁小，谁右移
int i=0,j=0;
int half = (nums1.length+nums2.length+1)>>1;
boolean lengthFlag = ((nums1.length+nums2.length) & 1)==0;
Integer temp1,temp0=null;
boolean flag1=true,flag2=true;
while (true){
if(i<nums1.length)
value1 = nums1[i];
if(j<nums2.length)
value2 = nums2[j];
//(如果 num1当前值小于num2当前值，且游标未到达num1的最右边) 或者 (num2右标已到达最右边，此时只移动num1)
if((value1<value2 && flag1) || !flag2){
if(i >= nums1.length){
flag1 = false;
continue;
}
temp1 = value1;
i++;
}else {
if(j >= nums2.length) {
flag2 = false;
continue;
}
temp1 = value2;
j++;
}
// 如果已经到了中位数的位置
if((i+j) == half){
// 两数组长为偶数时，需找两个值
if(lengthFlag){
if(temp0 == null){
half++;
temp0 = temp1;
continue;
}
return ((double) (temp1+temp0))/2d;
}else {
return temp1;
}
}
}
}Python版本
from typing import List
def getMiddleByTwoNumbers(nums1: List[int], nums2: List[int]) -> float:
value1=0
value2=0
i=0
j = 0
half = (len(nums1) + len(nums2) + 1) // 2
lengthFlag = (len(nums1) + len(nums2))%2 == 0
tempFlag = False
temp1=0
temp0=0
flag1 = True
flag2 = True
while True:
if i<len(nums1):
value1=nums1[i]
if j<len(nums2):
value2=nums2[j]
if (value1<value2 and flag1) or not flag2:
if i>= len(nums1):
flag1 = False
continue
temp1 = value1
i = i+1
else:
if j>= len(nums2):
flag2 = False
continue
temp1 = value2
j = j+1
if (i+j) == half:
if lengthFlag:
if not tempFlag:
tempFlag = True
half = half+1
temp0 = temp1
continue
return (temp0+temp1)/2
else:
return temp1Go版本
func getMiddleByTwoNumbers( num1 []int ,num2 []int) float64 {
var value1 int = 0
var value2 int = 0
// 声明两个游标
var i int = 0
var j int = 0
var half int = (len(num1)+len(num2)+1)/2
var lengthFlag bool = (len(num1)+len(num2))%2==0
// 两数组长度为偶数时，额外处理的开关
var even bool = false
var temp0 int
var temp1 int
var flag1 bool =true
var flag2 bool =true
for true{
if i<len(num1){
value1 = num1[i]
}
if j<len(num2){
value2 = num2[j]
}
if (value1<value2 && flag1) || !flag2 {
if i>= len(num1){
flag1=false
continue
}
temp1 = value1
i++
}else {
if j>= len(num2){
flag2=false
continue
}
temp1 = value2
j++
}
if (i+j) == half{
// 如果两数组长度和为偶数
if lengthFlag {
// 如果是false，说明中位数还需要拿一位
if !even {
half++
temp0 = temp1
even = true
continue
}
return float64(temp0+temp1)/2.0
}else {
return float64(temp1)
}
}
}
return float64(temp1)
}LeetCode运行结果
Java的优化确实已经登峰造极了，三种语言代码是一样的思路写的，Java还是跑的最快的，只不过内存用的有点多，毕竟Java有个JVM在那
