通州顺德网站建设,企业自助网站建设,国外品牌vi设计,包车哪个网站做的最好给你两个按 非递减顺序 排列的整数数组 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 。Python方法一#方法1
class Solution(object):def merge(self, nums1, m, nums2, n)::type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead.nums1[m:] nums2nums1.sort()print(nums1)快速排序的时间复杂度和空间复杂度https://blog.csdn.net/qq_35344198/article/details/106785849方法二双指针class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None:Do not return anything, modify nums1 in-place instead.sorted []p1, p2 0, 0while p1 m or p2 n:if p1 m:sorted.append(nums2[p2])p2 1elif p2 n:sorted.append(nums1[p1])p1 1elif nums1[p1] nums2[p2]:sorted.append(nums1[p1])p1 1else:sorted.append(nums2[p2])p2 1nums1[:] sortedpython的指针https://zhuanlan.zhihu.com/p/549404860nums1[:]sort和nums1sort第一种在原地址修改值 第二种修改nums1的指针到sort方法三逆向双指针尾插法class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None:Do not return anything, modify nums1 in-place instead.p1, p2 m - 1, n - 1tail m n - 1while p1 0 or p2 0:if p1 -1:nums1[tail] nums2[p2]p2 - 1elif p2 -1:nums1[tail] nums1[p1]p1 - 1elif nums1[p1] nums2[p2]:nums1[tail] nums1[p1]p1 - 1else:nums1[tail] nums2[p2]p2 - 1tail - 1总结方法一最简单方法二和方法三在时间复杂度上一致但是方法三的空间复杂度更低。从运行结果来看和网速有点关系内存的衡量每次也不太一样。JAVA方法1利用拼接后排序public void merge0(int[] nums1, int m, int[] nums2, int n){for(int i0;in;i){nums1[mi]nums2[i];}Arrays.sort(nums1);}方法2借助双指针 public void merge1(int[] nums1, int m, int[] nums2, int n) {int p1 0, p2 0,cur;int[] sort new int[mn];while (p1 m || p2 n) {if (p1 m) {curnums2[p2];p2 1;} else if (p2 n) {curnums1[p1];p1 1;} else if (nums1[p1] nums2[p2]) {cur nums2[p2];p2 1;} else {cur nums1[p1];p1 1;}sort[p1p2-1]cur;}for(int i0;i nums1.length;i){nums1[i]sort[i];}}
方法3借助逆向双指针在nums上操作 public void merge2(int[] nums1, int m, int[] nums2, int n) {int p1m-1,p2n-1,tail mn-1;while(p10 || p20){if(p1-1){nums1[tail]nums2[p2];p2-1;} else if (p2-1) {nums1[tail]nums1[p1];p1-1;} else if (nums1[p1]nums2[p2]) {nums1[tail]nums2[p2];p2-1;}else {nums1[tail]nums1[p1];p1-1;}tail-1;}}
