Leetcode原题
思路
拿到题目以后，我们还是由简单思路再到精妙的设计思路。 题目的要求是将nums1和nums2两个数组合并。且我们已经知道了nums1数组中前m个元素为需要合并的元素，后n个元素为0.
方法一 直接合并排序
那么我们的第一种想法，就是可以从nums1 中下标为m的元素开始，存储nums2的元素。然后再利用集合本身的排序方法进行排序
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); // System.out.println(Arrays.toString(nums1)); }
因为是利用了java本身的排序方法，我们看了一下是使用了快排算法
然后提交执行一下，居然才超过24.18%的用户 。。。
方法二 双指针
有没有其他的好方法呢，这里我看了一下官网的提示。它说方法1中，并没有利用两个数组已经被排序的性质。为了利用这个性质，我们可以使用双指针方法，将2个数组看做队列，每次从2个数组头部取出比较小的数字放在结果中。如下面的动画所示：
public void merge(int[] nums1, int m, int[] nums2, int n) { int len=m+n; int tem[]=new int[len];//定义一个临时数组 for (int index=0,nums1Index=0,nums2Index=0;index<len;index++){ if (nums1Index>=m){ //数组1已经取完，则完全取数组2即可 tem[index] =nums2[nums2Index++]; } else if (nums2Index>=n){ //数组2取完，则完全取数组1即可 tem[index] = nums1[nums1Index++]; }else if (nums1[nums1Index]< nums2[nums2Index]){ //数组1中的元素小于数组2中的元素，取数组1中的数即可 tem[index] = nums1[nums1Index++]; }else { tem[index] =nums2[nums2Index++]; } } for (int i = 0; i <len ; i++) { nums1[i]= tem[i]; } // System.out.println(Arrays.toString(nums1)); }
这个方法的时间复杂度为 O(M+n)。空间复杂度为O(m+n).多了一个中间数组tem。那么有没有办法省去tem.直接在nums1上操作即可。
方法三：逆向双指针
这种方法采用了逆向思维，通过观察我们可以发现nums1后半部分都是空的，我们可以直接覆盖。倒着将nums2的元素合并进来不就好了嘛。于是，我们可以使用指针从后向前遍历。每次取两者之间的较大值放在nums1的最后面
//倒序的方式插入 public void merge(int[] nums1, int m, int[] nums2, int n) { int len=m+n;//总元素长度 for (int index = len-1,nums1Index = m-1,nums2Index =n-1 ;index>=0; index--) { if (nums1Index <0){ //num1数已经取完，则取num2即可 nums1[index]=nums2[nums2Index--]; }else if (nums2Index <0){ //num2取完，则取num1本身即可 break; }else if (nums1[nums1Index]>nums2[nums2Index]){ nums1[index] =nums1[nums1Index--]; }else { //num2的元素大于等于num1的元素，取num2的值 nums1[index] =nums2[nums2Index--]; } } // System.out.println(Arrays.toString(nums1)); }
提交测试，超过了100%的用户，哈哈，妙啊
因为目前个人算法能力有限，有更好的方法的小伙伴可以在评论区留言分享，大家一起共同进步。
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取2022最新java面试资料以及简历模型120套哦~
