88. 合并两个有序数组(Merge Sorted Array)E

英文题目

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.
Example:
Input:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
Output: [1,2,2,3,5,6]

Constraints:
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n

中文题目

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明：
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例：
输入：

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出：[1,2,2,3,5,6]

提示：
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n

暴力解法

把数组nums2放到nums2尾部，然后排序即可
时间复杂度O( (m+n)log(m+n) )，序列长度是m+n，直接套用快排的时间复杂度

空间复杂度O(log(m+n) )

# python3: 时间 32 ms, 击败 95.11%; 内存 14.9 MB, 击败 34.68%
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()

// c++: 时间 4 ms, 击败 53.83%; 内存 8.9 MB, 击败 24.28%
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());
    }
};

// java: 时间 1 ms, 击败 28.48%; 内存 40.3 MB, 击败 59.47%
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; ++i) {
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

// go: 时间 0 ms, 击败 100%; 内存 2.2 MB, 击败 95.14%
func merge(nums1 []int, m int, nums2 []int, n int)  {
    copy(nums1[m:], nums2)
    sort.Ints(nums1)
}

// javascript: 时间 60 ms, 击败 74.88%; 内存 41.3 MB, 击败 21.41%
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m, ...nums2);
    nums1.sort((a,b) => a-b);
};

双指针

新开辟一个数组，排序后替换nums1

时间复杂度O(m+n)，空间复杂度O(m+n)

# python3: 时间 36 ms, 击败 84.02%; 内存 14.8 MB, 击败 77.58%
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        merged = []
        p1, p2 = 0, 0
        while p1 < m and p2 < n:
            if nums1[p1] <= nums2[p2]:
                merged.append(nums1[p1])
                p1 += 1
            else:
                merged.append(nums2[p2])
                p2 += 1
        merged.extend(nums1[p1:m])
        merged.extend(nums2[p2:])
        nums1[:] = merged

// c++: 时间 4 ms, 击败 53.83%; 内存 9 MB, 击败 11.19%
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> merged;
        int p1 = 0, p2 = 0;
        while (p1 < m && p2 < n) {
            if (nums1[p1] <= nums2[p2]) {
                merged.push_back(nums1[p1]);
                ++p1;
            } else {
                merged.push_back(nums2[p2]);
                ++p2;
            }
        }
        merged.insert(merged.end(), nums1.begin()+p1, nums1.begin()+m);
        merged.insert(merged.end(), nums2.begin()+p2, nums2.end());
        nums1 = merged;
    }
};

// java: 时间 0 ms, 击败 100%; 内存 39.9 MB, 击败 97.88%
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] merged = new int[m+n];
        int p1 = 0, p2 = 0;
        int cur = 0;
        while (p1 < m && p2 < n) {
            if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1];
                ++p1;
            } else {
                cur = nums2[p2];
                ++p2;
            }
            merged[p1+p2-1] = cur;
        }
        while (p1 < m) {
            merged[p1+p2] = nums1[p1];
            ++p1;
        }
        while (p2 < n) {
            merged[p1+p2] = nums2[p2];
            ++p2;
        }
        for (int i = 0; i < merged.length; ++i) {
            nums1[i] = merged[i];
        }
    }
}

// go: 时间 0 ms, 击败 100%; 内存 2.2 MB, 击败 17.24%
func merge(nums1 []int, m int, nums2 []int, n int)  {
    merged := make([]int, 0, m+n)
    p1, p2 := 0, 0
    for p1 < m && p2 < n {
        if (nums1[p1] < nums2[p2]) {
            merged = append(merged, nums1[p1])
            p1++
        } else {
            merged = append(merged, nums2[p2])
            p2++
        }
    }
    merged = append(merged, nums1[p1:m]...)
    merged = append(merged, nums2[p2:]...)
    copy(nums1, merged)
}

// javascript: 时间 56 ms, 击败 89.79%; 内存 41.3 MB, 击败 16.29%
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let merged = new Array();
    let p1 = 0, p2 = 0;
    while (p1 < m && p2 < n) {
        if (nums1[p1] < nums2[p2]) {
            merged.push(nums1[p1]);
            ++p1;
        } else {
            merged.push(nums2[p2]);
            ++p2;
        }
    }
    merged = merged.concat(nums1.slice(p1, m));
    merged = merged.concat(nums2.slice(p2, n));
    for (let i = 0; i < m+n; ++i) {
        nums1[i] = merged[i];
    }
};

逆向双指针

从后往前遍历即可

时间复杂度O(m+n)，空间复杂度O(1)

# python3: 时间 36 ms, 击败 85.59%; 内存 16.1 MB, 击败 41.38%
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m-1, n-1
        cur = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[cur] = nums1[p1]
                p1 -= 1
            else:
                nums1[cur] = nums2[p2]
                p2 -= 1
            cur -= 1
        # 此处只需要判断nums2即可，不需要判断nums1
        # 原因是，如nums2已走完，nums1必然有序
        while p2 >= 0:
            nums1[cur] = nums2[p2]
            p2 -= 1
            cur -= 1

// c++: 时间 4 ms, 击败 53.83%; 内存 8.8 MB, 击败 71.38%
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m-1, p2 = n-1;
        int cur = m+n-1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[cur] = nums1[p1];
                --p1;
            } else {
                nums1[cur] = nums2[p2];
                --p2;
            }
            --cur;
        }
        while (p2 >= 0) {
            nums1[cur] = nums2[p2];
            --p2;
            --cur;
        }
    }
};

// java: 时间 0 ms, 击败 100%; 内存 40.2 MB, 击败 74.88%
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1, p2 = n-1;
        int cur = m+n-1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[cur] = nums1[p1];
                --p1;
            } else {
                nums1[cur] = nums2[p2];
                --p2;
            }
            --cur;
        }
        while (p2 >= 0) {
            nums1[cur] = nums2[p2];
            --p2;
            --cur;
        }
    }
}

// go: 时间 0 ms, 击败 100%; 内存 2.2 MB, 击败 89.20%
func merge(nums1 []int, m int, nums2 []int, n int)  {
    p1, p2 := m-1, n-1
    cur := m+n-1
    for p1 >= 0 && p2 >= 0 {
        if nums1[p1] > nums2[p2] {
            nums1[cur] = nums1[p1]
            p1--
        } else {
            nums1[cur] = nums2[p2]
            p2--
        }
        cur--
    }
    for p2 >= 0 {
        nums1[cur] = nums2[p2]
        p2--
        cur--
    }
}

// javascript: 时间 60 ms, 击败 74.88%; 内存 41.1 MB, 击败 63.19%
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let p1 = m-1, p2 = n-1;
    let cur = m+n-1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[cur] = nums1[p1];
            --p1;
        } else {
            nums1[cur] = nums2[p2];
            --p2;
        }
        --cur;
    }
    while (p2 >= 0) {
        nums1[cur] = nums2[p2];
        --p2;
        --cur;
    }
};

也可两个循环合并在一起，但个人感觉上面的写法更易懂，写法如下：

# python3: 时间 32 ms, 击败 95.11%; 内存 14.8 MB, 击败 86.42%
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1
        # cur为nums1排序后的索引下标
        for cur in range(m + n - 1, -1, -1):
            # 此处可进行优化，原因是，当nums2已走完
            # 此时nums1必然已经有序，可直接返回
            if p2 == -1:
                return
            elif p1 == -1 or nums1[p1] < nums2[p2]:
                nums1[cur] = nums2[p2]
                p2 -= 1
            else: # nums1[p1] >= nums2[p2]:
                nums1[cur] = nums1[p1]
                p1 -= 1

// c++: 时间 4 ms, 击败 64.59%; 内存 8.6 MB, 击败 99.87%
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m-1, p2 = n-1;
        for (int cur = m+n-1; cur >= 0; --cur) {
            if (p2 == -1) {
                return;
            } else if (p1 == -1 || nums1[p1] <= nums2[p2]) {
                nums1[cur] = nums2[p2];
                --p2;
            } else {
                nums1[cur]  = nums1[p1];
                --p1;
            }
        }
    }
};

# 88. 合并两个有序数组(Merge Sorted Array)E

# 英文题目

# 中文题目

# 暴力解法

# 双指针

# 逆向双指针

88. 合并两个有序数组(Merge Sorted Array)E

英文题目

中文题目

暴力解法

双指针

逆向双指针