登录
  • #打卡
  • #打卡组队

300+弱鸡重刷leetcode(附题目总结)

Zheyuuu
3310
46
### [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):

如果觉得楼主哪里写的有问题的话,欢迎指出噢~
46条回复
热度排序

发表回复