Algorithm 1 归并排序

题目:

https://leetcode.com/problems/merge-sorted-array/description

要点:

要求线性时间, 因此不能使用std::sort(), 后者是 O(n * log(n))
按照题目提示需要注意到数组m有额外空间, 因此我们需要利用m尾部的空间
1. 不要额外开空间
2. 从后往前排序以避免从前往后排序时需要进行的临时存储

解法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p3 = m + n - 1;

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

错误1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p3 = m + n - 1;

        while (p3 >= 0) { //p3虽然在正确情况下也是满足这个条件的, 但是
            if (p1 >= 0 && nums1[p1] > nums2[p2]) { //这里要解引用p2, 所以不能while p3 而是p2
                nums1[p3--] = nums1[p1--]; //p3不需要校验, 因为p2自动对齐了p3
            } else {
                nums1[p3--] = nums2[p2--];
            }
        }
    }
};

错误2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p3 = m + n - 1;

        while (p2 >= 0) { 
            if (nums1[p1] > nums2[p2]) { //没有检验解引用的下标, 
            //注意: while+if替代for循环的部分功能时, 需要正确的初始化, 正确的判断条件, 正确的递增或递减下标
                nums1[p3--] = nums1[p1--]; 
            } else {
                nums1[p3--] = nums2[p2--];
            }
        }
    }
};