[LeetCode][Java] Merge Sorted Array

题目：

Given two sorted integer arraysnums1andnums2, mergenums2intonums1as one sorted array.

Note:You may assume thatnums1has enough space (size that is greater or equal tom+n) to hold additional elements fromnums2. The number of elements initialized innums1andnums2aremandnrespectively.

题意：

注意：

）从而能够包含来自nums2 的额外的元素。

算法分析：

方法一：

第一次AC时没有考虑过多的空间复杂度的事情，开辟了一个新的数组来包含num1和nums2中的合并元素，然后在用这个新的数组重新覆盖nums1.

利用两个指针，分别遍历nums1和nums2，比较其中比较大的元素放入新的数组中。

方法二：

对每个数组维护一个指针，然后比较指针所指的值，每次迭代中A和B指向的元素大的便加入结果数组中，，然后index-1，另一个不动。这里从后往前扫是因为这个题目中结果仍然放在A中，如果从前扫会有覆盖掉未检查的元素的可能性。

AC代码：

方法一：

<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution {public void merge(int[] nums1, int m, int[] nums2, int n){if(n == 0)return;if(m == 0){for(int i=0;i<n;i++){nums1[i]=nums2[i];}return;}int nums1index=0;int nums2index=0;int newnums[]=new int[m+n];int i=0;while(nums1index<=m-1&&nums2index<=n-1)//两个数组中公共长度部分{if(nums1[nums1index]<nums2[nums2index]){newnums[i]=nums1[nums1index];nums1index++;i++;}else{newnums[i]=nums2[nums2index];nums2index++;i++;}}while(nums1index<=m&&nums2index<=n){if(nums1index==m&&nums2index<=n-1)//数组二多于数组一的情况{newnums[i]=nums2[nums2index];nums2index++;i++;}else if(nums2index==n&&nums1index<=m-1)//数组一多于数组二的情况{newnums[i]=nums1[nums1index];nums1index++;i++;}elsebreak;}for(i=0;i<m+n;i++)nums1[i]=newnums[i];}}</span>方法二：

<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution {public void merge(int A[], int m, int B[], int n){while(m > 0 && n > 0){if(A[m-1] > B[n-1]){A[m+n-1] = A[m-1];m–;}else{A[m+n-1] = B[n-1];n–;}}while(n > 0){A[m+n-1] = B[n-1];n–;}}}</span>

版权声明：本文为博主原创文章，转载注明出处

去陌生的街角，去做一切我们曾经或现在也很想做的事情，