合肥做网站加盟,做app网站的软件有哪些内容吗,vi设计公司[本源百纳设计,服务器怎么建网站面试经典 150 题 ---- 合并两个有序数组 合并两个有序数组方法一#xff1a;直接合并后排序方法二#xff1a;双指针方法三#xff1a;逆向双指针 合并两个有序数组
方法一#xff1a;直接合并后排序
这种方法最简单#xff0c;直接将 nums2 的数组放到 nums1 数组的尾部… 面试经典 150 题 ---- 合并两个有序数组 合并两个有序数组方法一直接合并后排序方法二双指针方法三逆向双指针 合并两个有序数组
方法一直接合并后排序
这种方法最简单直接将 nums2 的数组放到 nums1 数组的尾部然后对 nums1 进行排序即可
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for (int i 0; i n; i ) {nums1[i m] nums2[i];}Arrays.sort(nums1);}
}时间复杂度 O((m n)log(m n)) 数组长度为 m n快排的时间复杂度为 O((m n)log(m n))
空间复杂度 O((m n)log(m n)) 数组长度为 m n快排的时间复杂度为 O((m n)log(m n))
方法二双指针
方法一没有使用到数组已经被排序的性质。利用这一性质我们可以使用双指针方法。将两个数组看作队列每次从数组的头部取出一个比较小的值放到结果中。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 0, p2 0;int[] sorted new int[m n];int cur 0;while (p1 m || p2 n) {if (p1 m) {sorted[cur] nums2[p2];} else if (p2 n) {sorted[cur] nums1[p1];} else if (nums1[p1] nums2[p2]) {sorted[cur] nums1[p1];} else {sorted[cur] nums2[p2];}cur ;}for (int i 0; i m n; i ) {nums1[i] sorted[i];}}
}时间复杂度 O(m n) 指针单调移动最多移动 m n 次因此时间复杂度为 O(m n)
空间复杂度 O(m n) 需要建立长度为 m n 的中间数组
方法三逆向双指针
方法二需要使用临时变量是因为直接合并到 nums1 中nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢可以使用双指针从后往前遍历每次取两者之中的比较大者放进 nums1 的最后面。 为什么从后往前将大的元素放入到 nums1 中就不会出现覆盖元素的情况呢 可以这样想象。如果是将 nums2 中的元素放入了 nums1 中那么此时 nums1 的元素肯定不会被覆盖如果是将 nums1 中的元素放入了 nums1 的后半部分nums1 的前半部分就肯定会出现一个空位从而保证全部元素都可以放进去且不会发生覆盖。 class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1, p2 n - 1;int cur nums1.length - 1;while(p1 0 || p2 0) {if (p1 -1) {nums1[cur -- ] nums2[p2 -- ];} else if (p2 -1) {nums1[cur -- ] nums1[p1 -- ];} else if (nums1[p1] nums2[p2]) {nums1[cur -- ] nums1[p1 -- ];} else {nums1[cur -- ] nums2[p2 -- ];}}}
}时间复杂度 O(m n) 指针单调移动最多移动 m n 次因此时间复杂度为 O(m n)
空间复杂度 O(m n) 直接对 nums1 原地修改不需要额外的空间
