佛山微网站建设报价,网站制作问题 图片版权,广西建设网郭业棚,网站开发下载那个题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 排列。
注意#xff1a;最终#xff0c;合并…题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-109 nums1[i], nums2[j] 109
解答
方法1: 合并后使用系统方法 sort() (最简单, 最直接)
Show Code
class Solution {func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {// range operator (区间运算符/区间操作符)for idx in 0..n {nums1[m idx] nums2[idx]}// 闭包表达式的简短方式nums1.sort(by: )}
}复杂度分析 时间复杂度O((mn)log(mn)) 排序序列长度为 mn套用 sort 方法的时间复杂度即可平均情况为 O((mn)log(mn)) 空间复杂度: O(mn) 排序序列长度为 mn套用sort 方法的空间复杂度即可平均情况为 O(mn) Swift 的内置排序算法 sort() 在 Swift5 之后采用了 TimSort相较于之前的 Introsort 更 stability, 什么是 stability它是_一种排序后维持相等元素的原始顺序的能力_, 关于 Swift 中 sort() 的 stability, 可以参考 Is sort() stable in Swift 5? TimSort 是一种混合算法 包含插入排序O(n^2) 和 归并排序O(nlogn) 因为 插入 和 归并 都是 stability 所以 TimSort 也是 TimSort 核心原理是 切割 合并, 具体实现可参考 TimSort TimSort 的平均时间复杂度为O(nlogn) 最好情况O(n) 最差情况O(nlogn) 。 空间复杂度O(n) 是一个稳定的排序算法。 自该算法被发明以来已被Python、Java、Android 平台和GNU Octave 用作默认排序算法。 执行用时内存消耗 方法2: 双指针
方法一没有利用数组 nums1 与 nums2 已经被排序的性质。为了利用这一性质我们可以使用双指针方法。这一方法将两个数组看作队列每次从两个数组头部取出比较小的数字放到结果中。
Show code func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {var p1 0, p2 0var sorted [Int]()while p1 m || p2 n {if p1 m {sorted.append(nums2[p2])p2 1// 很重要, 没有则会向下执行, 最终Crash - Fatal error: Index out of rangecontinue}if p2 n {sorted.append(nums1[p1])p1 1// 很重要, 没有则会向下执行, 最终Crash - Fatal error: Index out of rangecontinue}if nums1[p1] nums2[p2] {sorted.append(nums1[p1])p1 1} else {sorted.append(nums2[p2])p2 1}}for idx in 0..(mn) {nums1[idx] sorted[idx]}}复杂度分析 时间复杂度: O(m n) 指针移动单调递增最多移动 mn 次因此时间复杂度为 O(mn) 空间复杂度: O(m n) 需要建立长度为 mn 的中间数组 sorted
方法3: 逆向双指针
方法二中之所以要使用临时变量是因为如果直接合并到数组 nums1 中nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢观察可知nums1 的后半部分是空的可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历每次取两者之中的较大者放进 nums1 的最后面。
严格来说在此遍历过程中的任意一个时刻nums1 数组中有 m−p1−1 个元素被放入 nums1 的后半部nums2 数组中有 n−p2−1 个元素被放入 nums1 的后半部而在指针 p1 的后面nums1 数组有 mn−p1−1 个位置。由于
mn−p1−1≥m−p1−1n−p2−1
等价于
p2≥−1
永远成立因此 p1 后面的位置永远足够容纳被插入的元素不会产生 p1 的元素被覆盖的情况。
Show code func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {var p1 m - 1, p2 n - 1var tail m n - 1while p1 -1 || p2 -1 {if p1 -1 {nums1[tail] nums2[p2]tail - 1p2 - 1continue}if p2 -1 {nums1[tail] nums1[p1]tail - 1p1 - 1continue}if nums1[p1] nums2[p2] {nums1[tail] nums1[p1]p1 - 1tail - 1} else {nums1[tail] nums2[p2]p2 - 1tail - 1}}}复杂度分析 时间复杂度: O(m n) 指针移动单调递减最多移动 mn 次因此时间复杂度为 O(mn) 空间复杂度: O(1) 直接对数组 nums1 原地修改不需要额外空间
