清风的技术小屋

不为所动, 做更专业的自己

0%

LeetCode 88 - Merge Sorted Array

问题描述:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题目中说数组nums1大小为 m,数组nums2的大小为 n,要将数组nums2中的元素全部放到数组nums1中且保证数组nums1有序(这里有序假设是从小到大)。

时间复杂度为 O(nm) 的解法

初看到这个题目,一个最直观的想法就是设定两个指针分别指向两个数组开始的元素(令指针p1指向数组nums1,p2指向数组p2),然后从头开始遍历两个数组。

  • 如果指针p1指向的元素小于等于指针p2指向的元素,指针p1加一。
  • 如果指针p1指向的元素大于指针p2指向的元素,将指针p2指向的元素插入到指针p1指向的位置,指针p1指向的位置后面的元素都后移一位,指针p1和指针p2都加一。

这样操作直到数组nums1或数组nums2的元素遍历完,如果是数组nums1的元素先被遍历完,则将数组nums2剩下的元素都复制到数组nums1中,如果是数组nums2的元素先被遍历完,算法停止。在最坏的情况下,数组nums2的元素都小于数组nums1的元素,每次插入数组nums2的元素,都要移动数组nums1的 \(O(m)\) 个字符,那么算法复杂度为 \(O(nm)\)

时间复杂度为 O(n + m) 的解法

换个思路,我们不从头开始遍历数组,而是从数组后面开始遍历数组。这里我们准备三个指针:p、p1和p2,指针p指向数组nums1的第 n + m 个元素,指针p1指向数组nums1最后一个元素,指针p2指向数组nums2的最后一个元素。

  • 如果指针p1指向的元素小于指针p2指向的元素,将指针p2指向的元素复制到指针p指向的位置,指针p和p2减一。
  • 如果指针p1指向的元素大于等于指针p2指向的元素,将指针p1指向的元素复制到指针p指向的位置,指针p和p1减一。

这样操作直到数组nums1或数组nums2被遍历完,如果是数组nums1先被遍历完,将数组nums2剩余的元素复制到数组nums1中,如果是数组nums2先被遍历完,则算法停止。从上面分析我们可以看出,只需要遍历一次数组nums1和数组nums2就行,不需要移动元素,因此这个算法的时间复杂度为 \(O(n + m)\)

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
57
58
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

if (m <= 0)
nums1 = nums2;
if (n <= 0)
return;

int p, p1, p2;
p1 = m - 1;
p2 = n - 1;
p = m + n - 1;

while (p >= 0 && p1 >= 0 && p2 >= 0) {
if (nums1[p1] >= nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else if (nums1[p1] < nums2[p2]) {
nums1[p] = nums2[p2];
p2--;
}
p--;
}

if (p2 >= 0) {
while (p >=0 && p2 >=0)
nums1[p--] = nums2[p2--];
}
}
};

int main()
{
Solution solu;

vector<int> nums1 = {1, 3, 5, 7, 0, 0, 0};
vector<int> nums2 = {2, 4, 6};
solu.merge(nums1, 4, nums2, nums2.size());

for (auto it=nums1.begin(); it!=nums1.end(); ++it)
cout << *it << " ";
cout << endl;

vector<int> nums3 = {0, 0, 3, 0, 0, 0, 0, 0, 0};
vector<int> nums4 = {-1, 1, 1, 1, 2, 3};
solu.merge(nums3, 3, nums4, nums4.size());

for (auto it=nums3.begin(); it!=nums3.end(); ++it)
cout << *it << " ";
cout << endl;

return 0;
}