面试经典 150 题 1 —（数组 / 字符串）— 88. 合并两个有序数组

88. 合并两个有序数组

方法一：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    	// 先无序合并，再排序
        for(int i = 0; i<n;i++){
            nums1[m+i] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};
1
2
3
4
5
6
7
8
9
10

方法二：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    	// 整理原数组，腾出空间
        nums1.erase(nums1.begin()+m,nums1.end());
        nums2.erase(nums2.begin()+n,nums2.end());
        vector<int> tmp;
        while (n && m) {
        	// 不断调整原来的两个数组，每次选最小的放进tmp数组中
            if (nums1.front() <= nums2.front()) {
                tmp.push_back(nums1.front());
                nums1.erase(nums1.begin());
                m--;
            } else {
                tmp.push_back(nums2.front());
                nums2.erase(nums2.begin());
                n--;
            }
        }
		// num1中的元素全都被加入到tmp了，把num2剩下的放到末尾
        if (!m) {
            tmp.insert(tmp.end(), nums2.begin(), nums2.end());
            nums1 = tmp;
        }
        // num2中的元素全都被加入到tmp了，把num1剩下的放到末尾
        if (!n) {
            tmp.insert(tmp.end(), nums1.begin(), nums1.end());
            nums1 = tmp;
        }
    }
};
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

方法三：性能最好

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    	// p1指向num1中的元素，p2指向num2中的元素
        int p1 = 0, p2 = 0;
        int sorted[m + n];
        int cur;
        while (p1 < m || p2 < n) {
        	// 先遍历完num1
            if (p1 == m) {
                cur = nums2[p2++];
            } 
            // 先遍历完num2
            else if (p2 == n) {
                cur = nums1[p1++];
            } 
            // 利用p1和p2指针比较num1、num2中的元素，cur记录最小值
            else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
};
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