题目

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 greater or equal to m + n) to hold additional elements from nums2.

Example:

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

题意

将两个有序数组nums1和nums2合并成一个新的有序数组，且直接保存在nums1中。

思路

最简单的方法是新建一个m+n的新数组，归并排序后再复制到nums1中。但题目的意思很显然是不希望使用额外空间，因此可以采取以下做法：从nums1[m-1]和nums2[n-1]开始，向前遍历进行归并排序，将较大的值从nums1的m+n-1处开始依次向前存放。

代码实现

Java

  1. class Solution {
  2.     public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.         int i = m - 1, j = n - 1;
  4.         int p = m + n - 1;
  6.         while (i >= 0 && j >= 0) {
  7.             if (nums1[i] < nums2[j]) {
  8.                 nums1[p--] = nums2[j--];
  9.             } else {
  10.                 nums1[p--] = nums1[i--];
  11.             }
  12.         }
  14.         while (j >= 0) {
  15.             nums1[p--] = nums2[j--];
  16.         }
  17.     }
  18. }

JavaScript

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number} m
  4.  * @param {number[]} nums2
  5.  * @param {number} n
  6.  * @return {void} Do not return anything, modify nums1 in-place instead.
  7.  */
  8. var merge = function(nums1, m, nums2, n) {
  9.     let i = m - 1
  10.     let j = n - 1
  11.     let k = m + n - 1
  12.     while (i >= 0 && j >= 0) {
  13.         nums1[k--] = nums1[i] <= nums2[j] ? nums2[j--] : nums1[i--]
  14.     }
  15.     while (j >= 0) {
  16.         nums1[k--] = nums2[j--]
  17.     }
  18. }