重庆免费网站建设,5g站长工具查询,做网站和优化共多少钱,wordpress百家号插件88. 合并两个有序数组 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述
题目中转#xff1a;88. 合并两个有序数组
2.详细题解 两个数组均有序#xff08;非递减#xff09;#xff0c;要求合并两个数组#xff0c;直观的思路#xff0c;借助第三个数… 88. 合并两个有序数组 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述
题目中转88. 合并两个有序数组
2.详细题解 两个数组均有序非递减要求合并两个数组直观的思路借助第三个数组依次从左至右遍历两个数组比较二者大小将较小的依次放入第三个数组中遍历完毕后将第三个数组的元素再依次写入指定的第一个数组。但这样存在的问题是会有O(m1)的空间耗费因此充分利用第一个数组可以优化这部分空间耗费。 如果两个数组均从左至右遍历按照非递减顺序合并不借助第三者并不能完成合并而第一个数组后半部分n个长度是闲置的因此两个数组可以从右至左的顺序遍历按照非递增的顺序合并先定位大值元素的位置此时不用担心第一数组的空余位置不够用因为后半部分长度为第二个数组的长度肯定也会有疑问第一个数组不是也会把数据移入后半部分吗但忽略了第一个数组每移入一个数据到后半部分同时也会空出一个位置。 因此使用两个指针p1和p2分别指向两个数组中的最后一个元素索引即m-1和n-1当指针p1指向元素大于等于指针p2指向的元素时则将指针p1指向的元素移入指定位置并指针向左移动一位即p1–否则将指针p2指向的元素移入指定位置并指针向左移动一位即p2–;移入的位置也需要定位因此还需要第三个指针tail执行第一个数组的末尾即mn-1每移入一个元素则该指针向左移动一位即tail–。
3.代码实现
3.1 Python
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 and p2 0:if nums1[p1] nums2[p2]:nums1[tail] nums1[p1]p1 - 1else:nums1[tail] nums2[p2]p2 - 1tail - 1if p2 0:nums1[:p21] nums2[:p21]3.2 Java
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1;int p2 n - 1;int tail m n - 1;while (p1 0 p2 0){if (nums1[p1] nums2[p2]){nums1[tail--] nums1[p1--];}else{nums1[tail--] nums2[p2--];}}if (p2 0){for (int i0;ip2;i){nums1[i] nums2[i];}}}
}执行用时不必过于纠结对比可以发现对于python和java完全相同的编写java的时间一般是优于python的至于编写的代码的执行用时击败多少对手执行用时和网络环境、当前提交代码人数等均有关系可以尝试完全相同的代码多次执行用时也不是完全相同只要确保自己代码的算法时间复杂度满足相应要求即可也可以通过点击分布图查看其它coder的code
