继续创作，加快成长！这是我参与「日新方案 6 月更文挑战」的第4天，点击检查活动概况

前言

咱们社区连续会将顾毅（Netflix 增加黑客，《iOS 面试之道》作者，ACE 工作健身教练。）的 Swift 算法题题解收拾为文字版以便利咱们学习与阅览。

LeetCode 算法到现在咱们已经更新到 86 期，咱们会坚持更新时间和进展（周一、周三、周五早上 9:00 发布），每期的内容不多，咱们希望咱们能够在上班路上阅览，长久堆集会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。假如咱们有建议和意见欢迎在文末留言，咱们会尽力满意咱们的需求。

难度水平：简略

1. 描述

给你两个按 非递减次序 摆放的整数数组 nums1 和 nums2，还有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 兼并 nums2 到 nums1 中，使兼并后的数组相同按 非递减次序 摆放。

留意： 终究，兼并后数组不应由函数回来，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其间前 m 个元素表示应兼并的元素，后 n 个元素为 0 ，应疏忽。nums2 的长度为 n 。

2. 示例

示例 1

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解说：需求兼并 [1,2,3] 和 [2,5,6] 。
兼并结果是 [1,2,2,3,5,6] ，其间斜体加粗标注的为 nums1 中的元素。

示例 2

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解说：需求兼并 [1] 和 [] 。
兼并结果是 [1] 。

示例 3

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解说：需求兼并的数组是 [] 和 [1] 。
兼并结果是 [1] 。
留意，由于 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了保证兼并结果能够顺畅存放到 nums1 中。

约束条件：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9

3. 答案

 class MergeSortedArray {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var i = m - 1, j = n - 1
        while i >= 0 || j >= 0 {
            if j < 0 || (i >= 0 && nums1[i] > nums2[j]) {
                nums1[i + j + 1] = nums1[i]
                i -= 1
            } else {
                nums1[i + j + 1] = nums2[j]
                j -= 1
            }
        }
    }
}
  • 首要思维：兼并从尾到头，以防止掩盖。
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)

该算法题解的库房：LeetCode-Swift

点击前往 LeetCode 操练

关于咱们

咱们是由 Swift 爱好者共同保护，咱们会共享以 Swift 实战、SwiftUI、Swift 基础为中心的技能内容，也收拾收集优异的学习资料。