算法

合并两个有序数组

文章目录
  1. 1. 题目描述
  2. 2. 分析

合并两个有序数组

题目描述

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

1
2
3
4
5
6
7
8
9
10
说明:
初始化 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]

分析

有序数组合并，空间足够，那么不使用缓存处理

使用两个指针，分别指向两个数组的最后面
pt1 = m - 1
pt2 = n - 1
数组长度
len = 3 + 3
nums1 当前指针 curr = len - 1

因为 nums1 是连续的，nums2 放到 nums1 里面，那么当 nums2 遍历完后整个遍历就结束了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
  var cur = m + n - 1
  var idx1 = m - 1
  var idx2 = n - 1
  
  while idx2 >= 0 {
    if idx1 >= 0 && nums1[idx1] > nums2[idx2] {
      nums1[cur] = nums1[idx1]
      idx1 -= 1
    }else {
      nums1[cur] = nums2[idx2]
      idx2 -= 1
    }
    cur -= 1
  }
}