一、题目描述与分析
由题可知要合并nums1和nums2,并且nums1的长度为n+m。题目理解比较容易,直接看算法。
二、解题代码与算法描述
解决方法1
我们可以直接将nums1数组的0全部复制成nums2数组的元素值。然后再去进行排序。这也是我第一时间想到的算法。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i=0;i<n;i++){
nums1[m+i]=nums2[i];
}
Arrays.sort(nums1);
}
}
提交结果:
虽然可以通过,但这用到了java中的快速排序方法,时间复杂度较高。有什么更好的算法呢,仔细读题可发现,每个数组都是非递减排序。这也有了下面的算法。
解决方法2
我们可以用2个指针来分别对应数组,新建立一个空的数组,从小到大比较。nums1[nums1index]小于等于nums2[nums2index],就把小的值放到新数组,然后把nums1的索引值向后移一位再进行比较。反之也是一样。最后把新数组的值遍历都赋值给num1数组。这样就实现了。并且时间复杂度为O(n+m).
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//O(m+n)
int k=m+n;
int[] temp=new int[k];
for(int index=0,nums1index=0,nums2index=0;index<k;index++){
//nums1index>=m说明nums1数组值取完,直接取nums2数组值
if(nums1index>=m){
temp[index]=nums2[nums2index++];
}else if(nums2index>=n){//nums2index>=n说明nums2数组值取完,直接取nums1数组值
temp[index]=nums1[nums1index++];
}else if(nums1[nums1index]<= nums2[nums2index]){//数组1值小于数组二,所以把数组1该值赋值
temp[index]=nums1[nums1index++];
}else{//数组2值小于数组1,所以把数组2该值赋值
temp[index]=nums2[nums2index++];
}
}
//把数组赋值给数组1
for(int i=0;i<k;i++){
nums1[i]=temp[i];
}
}
}
提交结果:
也是超越了100%的用户。
这是从小到大取每一个数放到新的数组里,当然也可以不用新建数组。因为nums1数组已经有n长度的值为0的空间,所以可以从大到小赋值,指针先指向每个有效数组的最后一个有效元素(nums1index=m-1,nums2index=n-1)去比较大小,nums2[nums2index]>=nums1[nums1index]这就说明nums2[nums2index]值大,要放到后面,所以(nums1[m+n-1]=nums2[nums2index]),然后总指针-1,nums2index-1。反之也是一样。直到总指针减到0就完成了。这个是反向思路,其实就是正向思路的逆过程,大家可以去试试。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/114654.html