Catalog
  1. 1. 描述
  2. 2. 解析
  3. 3. 总结
LeetCode Solution: 4. Median of Two Sorted Arrays

描述

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

解析

解析1:暴力解法。

因为知道两个数组的长度

  1. 如果两数组长度之和为偶数,则中位数为第(m+n+1)/2与(m+n+2)/2之和的二分之一
  2. 如果两数组长度之和为奇数,则中位数为第(m+n+1)/2个数

循环遍历两个数组,抛弃掉小的那一个数,前进直到找到想要的数。

时间复杂度O(n)

解析2:利用二分法思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2)
{
int m = nums1.size();
int n = nums2.size();
int left = (m+n+1)/2;
int right = (m+n+2)/2;
bool odd = (m + n) / 2 != 0;

if(odd)
return (findKth(nums1, 0, nums2, 0, right)
+ findKth(nums1, 0, nums2, 0, left)) / 2.0;
else
return findKth(nums1, 0, nums2, 0, left);
}

static int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)
{
//the goal is to find the kth number in nums1 and nums2
if (i >= nums1.size())
//if i > nums1.size() return kth number in nums2;
return nums2[j+k-1];
if (j >= nums2.size())
return nums1[i+k-1];
if (k == 1)
return std::min(nums1[i], nums2[j]);

int midVal1 = (i + k/2 -1) < nums1.size() ? nums1[i+k/2-1] : INT_MAX;
int midVal2 = (j + k/2 -1) < nums2.size() ? nums2[j+k/2-1] : INT_MAX;

if (midVal1 < midVal2)
//weed out index i to k/2 of num1s
return findKth(nums1, i+k/2, nums2, j, k-k/2);
else
return findKth(nums1, i, nums2, j+k/2, k-k/2);
}
};

利用二分法的思想可以将时间复杂度降到O(log(m+n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2)
{
int m = nums1.size();
int n = nums2.size();
int left = (m+n+1)/2;
int right = (m+n+2)/2;
bool odd = (m + n) / 2 != 0;

if(odd)
return (findKth(nums1, 0, nums2, 0, right)
+ findKth(nums1, 0, nums2, 0, left)) / 2.0;
else
return findKth(nums1, 0, nums2, 0, left);
}

首先来看第一个函数,

  • m代表nums1的大小
  • n代表nums2的大小
  • left表示中间两个元素的左边那个
  • right表示中间元素的右边那个(如果为数组和大小为奇数时,leftright是相等的)
  • odd用来判断数组大小之和是否为奇数

最后判断一下,如果是奇数的话,只需要调用一次函数,避免函数调用的开销。

关键点在第二个函数上

1
int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)
  • i表示,数组一从index i开始
  • j表示,数组二从index j开始
  • k表示,要寻找的元素在第k位(从1开始算的第k位,不是index k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)
{
//the goal is to find the kth number in nums1 and nums2
if (i >= nums1.size())
return nums2[j+k-1];
if (j >= nums2.size())
return nums1[i+k-1];
if (k == 1)
return std::min(nums1[i], nums2[j]);

int midVal1 = (i + k/2 -1) < nums1.size() ? nums1[i+k/2-1] : INT_MAX;
int midVal2 = (j + k/2 -1) < nums2.size() ? nums2[j+k/2-1] : INT_MAX;

if (midVal1 < midVal2)
//weed out index i to k/2 of num1s
return findKth(nums1, i+k/2, nums2, j, k-k/2);
else
return findKth(nums1, i, nums2, j+k/2, k-k/2);
}
};

这个函数就是去想要一个概念数组,里面的元素是排好序的nums1和nums2,目的是为了淘汰第k位之前的元素以找到nums[k]

退出条件

  1. 如果i(j同理)(数组的起始位置)都比数组的大小还大了,那么说明要找的元素一定不在nums1里面,则把nums1的所有元素淘汰掉,直接返回nums2从j开始的第k位元素。

  2. 如果k==1的时候,表示从第i开始的第一个,只剩一个可以选择了,当然是选择两个之中小的一个 。

midVal1为数组1中间那个数,midVal2为数组2中间那个数,那么每次可以淘汰掉前k/2个,例如midVal2比midVal1小的时候,数组2以j开始的后k/2个数据只能作为我们要找的概念数组的第k个数据的垫脚石

当淘汰掉k/2后,需要找的元素就是index往后k/2后的第k/2个!

直到满足两个退出条件之一后退出即可

时间复杂度为O(log(m+n))

总结

这是一道很经典的题,思路也很新奇,在秋招的时候几个大厂出了这样的题,前几天面腾讯的时候面试官也问了。

记下来!

Author: Jsthcit
Link: http://jsthcitpizifly.com/2020/12/13/LeetCode-Solution-4/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶