- #打卡
- #打卡组队
300+弱鸡重刷leetcode（附题目总结）
Zheyuuu331046
### [4. 寻找两个有序数组的中位数](leetcode-cn.com)
时间复杂度要求O(log(m+n))
#### 解法一：
我自己想到的解法就是以两数组a,b 中所有元素的最小值和最大值为范围，在这个范围中二分搜索，每找到一个数k就判断一下是不是中位数。 这个判断的过程也就是 a,b中在找不大于k的元素个数之和是否等于
- (m+n+1)//2 对于a，b数组个数和为奇数
- (m+n+1)//2 or (m+n+2)//2 对于....偶数（有左中位数和右中位数）
那么怎么找不大于k的元素个数呢，其实可以转化为 二分查找 在数组中找>k的下界，所得left(第一个≥k的元素下标)即为数组中不大于k的元素个数。
总结一下，也就是两次二分，一次二分取值范围进行猜测(logK)，另一次对值利用二分进行判断(log(mn))， 所以总的复杂度至少是
logK ·log(mn)， 哇，惊人的复杂度...但是竟然还过了？？？
#### 解法二：
在题解中找到一份不错的[正确解法](leetcode-cn.com)，主要是利用了边界线的思想，这是条什么样的边界线呢？这条边界线将这两个数组各自分成了左右两部分， a,b左边部分的元素数量之和就是(m+n+1)/2，对于奇数数量的数组来说，第(m+n+1)/2个元素就是中位数，对于偶数数量的数组，是左中位数，别忘了还有右中位数。非常有意思的一条边界线，找到了它也就找到了中位数！
那怎样才能找到这样的边界线呢？由于a,b左边部分的元素数量之和就是(m+n+1)/2， 所以其实只要确定边界线在a中的索引，b自然确定， 那问题就转化成在数组中找索引，log(m+n)? 二分go!
大概知道二分还不够， 毕竟还是不知道具体怎么找orz...
接着分析， 从这条边界线在两个数组中的位置我们可以发现，这条边界线满足这样的性质：
1. 边界线左边的所有数都小于等于右边的所有数
2. - a,b元素和为奇数时, size左 = size右+1
- ...................偶数...., size左 = size右
性质2可以用 i+j=(m+n+1)//2 表示
性质1 就可以用来调整二分搜索的left right了，借用题解的图来表示一下逻辑
那这搜索的逻辑代码也就相应得出了：
```python
left = 0
right = m
while(left<right):
i = left + (right-left)//2
j = (m+n+1)//2 - i
if nums1 < nums[j-1]:
left = i+1
else:
right = i
```
所得 left 即为边界线
以为这样就完了吗？No！边界条件！如果边界线一侧是空集怎么办！
其实也可以处理， 先回想下，我们的边界线将两个数组分成两部分，左边一部分的元素的数量和是(m+n+1)/2，如果是m+n是奇数，那么就拿这第(m+n+1)/2个数，如果是偶数，那拿这个数和恰好比这个数大的那个数。
注意，是i+j=(m+n+1)/2，所以这第(m+n+1)/2个数是哪个呢？a在边界线左边的第一个数，还是b呢？对，比较一下这两个数谁大就行了，所以空集怎么处理也显而易见了吧，反正不可能选空集，那就把边界线左侧出现的空集表示成-inf。同样的逻辑，对于第(m+n+1)//2个数后的一个数，取边界线右侧a,b中更小的那个，出现空集就表示成inf
```python
nums1LeftMax = float("-inf") if i == 0 else nums1
nums1RightMin = float("inf") if i == len(nums1) else nums1
nums2LeftMax = float("-inf") if j == 0 else nums2[j- 1]
nums2RightMin = float("inf") if j == len(nums2) else nums2[j]
if (len(nums1) + len(nums2)) & 1:
return max(nums1LeftMax, nums2LeftMax)
else:
return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin))/2
```
至此，就解决了这个问题～
补充内容 (2020-2-4 02:09):
如果觉得楼主哪里写的有问题的话，欢迎指出噢～
时间复杂度要求O(log(m+n))
#### 解法一：
我自己想到的解法就是以两数组a,b 中所有元素的最小值和最大值为范围，在这个范围中二分搜索，每找到一个数k就判断一下是不是中位数。 这个判断的过程也就是 a,b中在找不大于k的元素个数之和是否等于
- (m+n+1)//2 对于a，b数组个数和为奇数
- (m+n+1)//2 or (m+n+2)//2 对于....偶数（有左中位数和右中位数）
那么怎么找不大于k的元素个数呢，其实可以转化为 二分查找 在数组中找>k的下界，所得left(第一个≥k的元素下标)即为数组中不大于k的元素个数。
总结一下，也就是两次二分，一次二分取值范围进行猜测(logK)，另一次对值利用二分进行判断(log(mn))， 所以总的复杂度至少是
logK ·log(mn)， 哇，惊人的复杂度...但是竟然还过了？？？
#### 解法二：
在题解中找到一份不错的[正确解法](leetcode-cn.com)，主要是利用了边界线的思想，这是条什么样的边界线呢？这条边界线将这两个数组各自分成了左右两部分， a,b左边部分的元素数量之和就是(m+n+1)/2，对于奇数数量的数组来说，第(m+n+1)/2个元素就是中位数，对于偶数数量的数组，是左中位数，别忘了还有右中位数。非常有意思的一条边界线，找到了它也就找到了中位数！
那怎样才能找到这样的边界线呢？由于a,b左边部分的元素数量之和就是(m+n+1)/2， 所以其实只要确定边界线在a中的索引，b自然确定， 那问题就转化成在数组中找索引，log(m+n)? 二分go!
大概知道二分还不够， 毕竟还是不知道具体怎么找orz...
接着分析， 从这条边界线在两个数组中的位置我们可以发现，这条边界线满足这样的性质：
1. 边界线左边的所有数都小于等于右边的所有数
2. - a,b元素和为奇数时, size左 = size右+1
- ...................偶数...., size左 = size右
性质2可以用 i+j=(m+n+1)//2 表示
性质1 就可以用来调整二分搜索的left right了，借用题解的图来表示一下逻辑
那这搜索的逻辑代码也就相应得出了：
```python
left = 0
right = m
while(left<right):
i = left + (right-left)//2
j = (m+n+1)//2 - i
if nums1 < nums[j-1]:
left = i+1
else:
right = i
```
所得 left 即为边界线
以为这样就完了吗？No！边界条件！如果边界线一侧是空集怎么办！
其实也可以处理， 先回想下，我们的边界线将两个数组分成两部分，左边一部分的元素的数量和是(m+n+1)/2，如果是m+n是奇数，那么就拿这第(m+n+1)/2个数，如果是偶数，那拿这个数和恰好比这个数大的那个数。
注意，是i+j=(m+n+1)/2，所以这第(m+n+1)/2个数是哪个呢？a在边界线左边的第一个数，还是b呢？对，比较一下这两个数谁大就行了，所以空集怎么处理也显而易见了吧，反正不可能选空集，那就把边界线左侧出现的空集表示成-inf。同样的逻辑，对于第(m+n+1)//2个数后的一个数，取边界线右侧a,b中更小的那个，出现空集就表示成inf
```python
nums1LeftMax = float("-inf") if i == 0 else nums1
nums1RightMin = float("inf") if i == len(nums1) else nums1
nums2LeftMax = float("-inf") if j == 0 else nums2[j- 1]
nums2RightMin = float("inf") if j == len(nums2) else nums2[j]
if (len(nums1) + len(nums2)) & 1:
return max(nums1LeftMax, nums2LeftMax)
else:
return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin))/2
```
至此，就解决了这个问题～
补充内容 (2020-2-4 02:09):
如果觉得楼主哪里写的有问题的话，欢迎指出噢～
