[Leetcode][4. 寻找两个正序数组的中位数] 4种方法:合并数组,二分搜索,划分数组

By Long Luo

Leetcode 4. 寻找两个正序数组的中位数 ,这是一道很经典的题目,非常考察算法功底和逻辑思维能力,下面我们就通过几种解法来吃透这道题吧!

方法一:暴力法(合并数组)

思路与算法:

很直观的解法,先将两个数组按照元素大小合并为一个数组,然后根据新数组长度来决定返回值。

注意在合并数组时,要注意指针边界情况,不要越过数组边界。

代码如下所示:

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
} else if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}

int[] nums = new int[m + n];
int total = m + n;
for (int i = 0, j = 0, cnt = 0; cnt < total; ) {
if (i == m && j < n) {
nums[cnt++] = nums2[j++];
} else if (j == n && i < m) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] <= nums2[j]) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] > nums2[j]) {
nums[cnt++] = nums2[j++];
}
}

if (total % 2 == 0) {
return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
} else {
return nums[total / 2];
}
}

其实,在合并数组时,实际上只需要合并到 \(cnt=total/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
public double findMedianSortedArrays_bf_opt(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
} else if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}

int[] nums = new int[m + n];
int total = m + n;
for (int i = 0, j = 0, cnt = 0; cnt <= total / 2; ) {
if (i == m && j < n) {
nums[cnt++] = nums2[j++];
} else if (j == n && i < m) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] <= nums2[j]) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] > nums2[j]) {
nums[cnt++] = nums2[j++];
}
}

if (total % 2 == 0) {
return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
} else {
return nums[total / 2];
}
}

复杂度分析:

  • 时间复杂度:\(O(m+n)\),需要遍历 \(2\) 个数组。

  • 空间复杂度:\(O(m+n)\),开辟了一个新数组,长度为 \(m+n\)

方法二:合并数组(优化空间)

思路与算法:

方法一需要新建一个长度为 \(len = m + n\) 的数组,但实际上我们并不需要将两个数组真的合并,我们只需要找到中位数在哪里就可以了。

同方法一,用一个循环计数,判断当前是否已经到了中位数的位置,到了就结束循环,但是需要考虑一些边界情况:

  1. 总长度为奇数;
    • 需要知道第 \(\frac{len + 1}{2}\) 个数,遍历区间 \([0, \frac{len}{2}]\) 次,返回最后一次遍历的结果。
  2. 总长度为偶数;
    • 需要知道第 \(\frac{len}{2}\)\(\frac{len}{2} + 1\) 个数,遍历区间 \([0, \frac{len}{2}]\) 次,返回最后一次和上一次遍历的结果。
  3. \(nums1\) 或者 \(nums2\) 遍历完之后;
  4. \(nums1\)\(nums2\) 都没有遍历完。

我们需要用两个变量 \(left\)\(right\)\(right\) 保存当前循环的结果,在每次循环开始前将\(right\)的值赋给 \(left\),这样在最后一次循环的时候,\(left\) 将得到 \(right\) 的值,也就是上一次循环的结果,接下来 \(right\) 更新为最后一次的结果。

使用 \(2\) 个指针分别指向当前指向 \(nums1\) 数组和 \(nums2\) 数组的位置:

  1. 如果 \(p < m\)\(nums1[p] \le nums2[q]\),那么就可以后移了,\(p++\)

  2. 如果 \(q \ge n\),说明此时 \(nums2\) 已经没有数字了,\(p < m && (q \ge n || nums1[p] \le nums2[q])\)

代码如下所示:

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
39
40
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}

if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}

int len = m + n;
int p = 0;
int q = 0;
int left = 0;
int right = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (p < m && (q >= n || nums1[p] <= nums2[q])) {
right = nums1[p++];
} else {
right = nums2[q++];
}
}

if (len % 2 == 0) {
return (double) (left + right) / 2;
} else {
return right;
}
}

复杂度分析:

  • 时间复杂度:\(O(m+n)\),需要遍历 \(2\) 个数组。

  • 空间复杂度:\(O(1)\)

方法三:二分查找

思路与算法:

注意到两个数组都是排序数组,很明显我们可以使用二分查找算法。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}

public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数
*/

int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;

while (true) {
// 边界情况
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}

// 正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}

复杂度分析:

  • 时间复杂度:\(O(\log (m+n))\),其中 \(m\)\(n\) 分别是数组 \(\textit{nums}_1\)\(\textit{nums}_2\) 的长度。初始时有 \(k=(m+n)/2\)\(k=(m+n)/2+1\),每一轮循环可以将查找范围减少一半,因此时间复杂度是 \(O(\log(m+n))\)

  • 空间复杂度:\(O(1)\)

方法四:二分查找

思路与算法:

注意到两个数组都是排序数组,很明显我们可以使用二分查找算法。

1

复杂度分析:

  • 时间复杂度:\(O(\log (m+n))\),其中 \(m\)\(n\) 分别是数组 \(\textit{nums}_1\)\(\textit{nums}_2\) 的长度。初始时有 \(k=(m+n)/2\)\(k=(m+n)/2+1\),每一轮循环可以将查找范围减少一半,因此时间复杂度是 \(O(\log(m+n))\)

  • 空间复杂度:\(O(1)\)


All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗