Leetcode 88.合并两个有序数组

题目是这样的：
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.

稍微翻译一下：
给定两个整型数组nums1和nums2,将nums2就地连接到nums1上，并保持升序。

说明：给定了m作为nums1有效初始数组的大小，n作为nums2有效初始数组的大小。可以假设nums1有足够的空间容纳nums2的所有元素。

注：有效初始数组表示首位不为0

###解题思路：

法一:

因为题目要求只能原地修改num1,因此可以使用sort方法()

*时间复杂度O( (m+n) log(m+n))

因为sorted和sort采用二分法排序

空间复杂度O(1)

sort()并没有开辟空间

法二:

同样对于解决数组问题，可以使用双指针，一个指针控制nums1[:m]的移动，另一个指针控制nums2的移动。又因为len(nums1[:m])和

len(nums2)不一定相同，所以添加额外条件。

# 因为nums1和num2的数组不一样，当一方的数组遍历完，那么直接将对方数组添加到nums1后面
 if i == m or j == n:
       if i == m and j != n:
           nums1[k] = nums2[j]
           j += 1
           continue
       if i != m and j == n:
           nums1[k] = temp[i]
           i += 1
           continue

#### **文文请看下面java语言的**

代码

Python

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.
        """
        # sort()方法实现
        if nums1 is None or nums2 is None:
            return nums1
        nums1[m:m+n] = nums2
        return nums1.sort()

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 双指针,牺牲空间换取时间
        temp = nums1[:m]
        i = 0
        print(temp)
        j = 0
        for k in range(m+n):
            if i == m or j == n:
                if i == m and j != n:
                    nums1[k] = nums2[j]
                    j += 1
                    continue
                if i != m and j == n:
                    nums1[k] = temp[i]
                    i += 1
                    continue
            if temp[i] < nums2[j]:
                nums1[k] = temp[i]
                i += 1
            else:
                nums1[k] = nums2[j]
                j += 1
        return nums1

Java

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
  }
}

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    //双指针
    //为nums1创建一个副本
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // 指定两个指针初始值
    int p1 = 0;
    int p2 = 0;

    // 为nums1设置一个指针
    int p = 0;

    //比较temp和nums2,将最小的添加到nums1中
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    //如果一方数组添加完毕，那么直接将另一方数组直接填到num1中
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}