LeetCode第[88]题(Java):Merge Sorted Array(合并已排序数组)

时间:2022-06-03 15:40:45

题目:合并已排序数组

难度:Easy

题目内容

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

翻译

给定两个排序的整数数组nums1和nums2,将nums2合并到nums1中作为一个排序数组。

注意:

nums1和nums2中初始化的元素数量分别为m和n。

nums1有足够的空间(大小大于或等于m+n)来容纳nums2中的额外元素。

 

我的思路:此处和归并排序中的小段归并有点像,不一样的地方在于在于其中nums1数组的长度是合并之后的长度。

     这样一来用传统的归并排序中的合并就不行了,因为在合并过程中可能将nums1数组中的数覆盖掉(eg.【4,5,0,0】【1,2】)

         除非再新建一个临时数组,将二者合并一起放入此数组中,然后再将此数组的值全部复制到nums1,那这样nums1的长度就没什么意义了。

     所以可以考虑归并排序的第二种方法———插入排序。原理不再赘述。把nums2直接当作接在nums1后面的数即可。

      三个指针:i 表示此时nums2的位置(从0开始);j表示此时nums1的位置(从m-1开始);k表示内部循环中nums1的位置。

 

我的代码

 1     public void merge(int[] nums1, int m, int[] nums2, int n) {
 2         int j = m - 1;
 3         for (int i = 0; i < n; i++) {
 4             if (j == -1 || nums2[i] >= nums1[j] ) {
 5                 while (i < n) {
 6                     nums1[++j] = nums2[i++];
 7                 }
 8                 return;
 9             } else {
10                 int k = j;
11                 for (; k > -1 && nums1[k] > nums2[i]; k--) {
12                     nums1[k+1] = nums1[k];
13                 }
14                 nums1[k+1] = nums2[i];
15                 j++;
16             }
17         }
18     }

我的复杂度:O(N*M)  空间复杂度  O(1)

编码过程中的问题

1、第4行,当m==0的时候,nums1内也是有一个0的,此时如果不加以判断,就会把0当作元素直接进入归并排序中去,然后就会越界,所以加入 j == -1 || 。

  eg.【0】m=0【1】n=1。

2、第15行,忘记了此时放入了一个,nums1的指针需要向右移动一个 ——  j++

 

答案代码

1 public void merge(int A[], int m, int B[], int n) {
2     int i = m-1, j = n-1, k = m+n-1;
3     while (i>-1 && j>-1)
4         A[k--] = A[i] > B[j]  ? A[i--] : B[j--];
5     while (j>-1)        
6         A[k--] = B[j--];
7 }

答案思路

既然从前往后会覆盖到,但是后面全是0,那么从后往前就不会覆盖到了。

(就算极端情况,A内全部小于B,后面的0刚好够B放,不会出现覆盖情况)

1、当 i 且 j 都没消耗完时,从后往前,谁大谁就入,并且相应指针消耗1;

2、如果 j 还没消耗完,则将B内剩下的都放入A;(此时如果A没消耗完也不需要管了,因为本来就已经在A里面按顺序排好了)