1.1. 题目

1.1.1. 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

• 初始化 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]

1.1.2. 题解:

• 两个数组是有序的,nums1数组除了正常值之外,还填充了nums2大小的零值
• m表示nums1里原有的值(除去填充位的),n 表示nums2原有的值
• 注意nums1 nums2 的值可能为0或者负数....,所以不要用0做判断
• 注意nums1可能等于nums2

1.1.3. 思路:

• 没有限定时间复杂度等,那就简单了
• 第一思路:
  • 直接将切片nums2合并到nums1里,然后对nums1进行sort排序即可
• 第二思路:
  • 两个指针分别从nums1和nums2往后移动和比较,把新结果放入到新的数组里
  • 因为没有返回值(直接取的nums1),所以需要把新数组再修改回到nums1上
• 第三思路:
  • 上面的第一思路的时间复杂度比较高,第二思路需要非常数的空间复杂度,所以还有个方法,直接在nums1上操作,这样时间复杂度和空间复杂度都降到最低
  • 双指针从两切片从后往前移动
  • 步骤:
    • nums1 := []int{1,2,4,6,0,0}
    • nums2 := []int{3,7}
    • 定义 n1 ,n1 默认值是nums1的长度,m,n是上面的原题里的值
    • 第一步:先比较nums1[m] = 6 与 nums2[n] = 7, 7比较大,那么把7放入到 nums1的n1位置,那么nums1现在就是 []int{1,2,4,6,0,7}
    • 第二步: 因为nums2已经挪走一个,那么n--,n1被占用一个,n1--
    • 第三步, 比较nums1[m] = 6 与 nums2[n] = 3, 6比较大,那么把6放入到 nums1的n1位置,那么nums1现在就是 []int{1,2,4,6,6,7}
    • 第四步: 因为nums1已经挪后一个,那么m--,n1被占用一个,n1--
    • 第五步 ....
    • 如果最后 nums2先走完,那么剩下的nums1就不需要再变化
    • 如果最后 nums1先走完,那么说明nums2剩下的值肯定都比nums1最小的还要小,这时候需要把nums1的前n1位替换成nums2的前n位
    • 不信你nums2 := []int{-11,-1}试试
  • 已写思路三的代码

1.1.4. 代码:

 n1 := len(nums1)

    for n1 > 0 && n > 0 {
        if m <= 0 {
            for k,v := range nums2[:n] {
                nums1[k] = v
            }
            break
        }
        // 此处赋值是为了方便debug..... 
        a1,a2 := nums1[m-1],nums2[n-1]
        if a1 > a2 {
            nums1[n1-1] = a1
            n1--
            m--
        } else if a1 <= a2 {
            nums1[n1-1] = a2
            n1--
            n--
        }
    }

代码