leetcode 88.Merge Sorted Array

2017-07-30

题意

合并两个排好序的数组1和数组2，假设数组1够大。最后返回数组1

我的思路

因为他是想返回数组1，所以在合并的时候会移动数组1，导致步骤增多。所以我想到开辟一个n+m的动态空间来存排序好的空间。最后赋值给数组1.这样能做到o(n+m)级的效率

代码

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] nums = new int[n+m];
    int index1 = 0;
    int index2 = 0;
    int index = 0;
    while(index1<m&&index2<n){
        if(nums1[index1]>nums2[index2]){
            nums[index++] = nums2[index2];
            index2++;
        }else{
            nums[index++] = nums1[index1];
            index1++;
        }
    }
    if(index1<m){
        while(index1<m)
            nums[index++] = nums1[index1++];
    }
    if(index2<n){
        while(index2<n)
            nums[index++] = nums2[index2++];
    }
    for(int i=0;i<n+m;i++){
        nums1[i] = nums[i];
    }
}

大神思路

和我思路不同的地方，不需要开辟多余的空间。

只需要从后开始比对数组大小就行。

大神代码

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i=m-1;
		int j=n-1;
		int k = m+n-1;
		while(i >=0 && j>=0)
		{
			if(A[i] > B[j])
				A[k--] = A[i--];
			else
				A[k--] = B[j--];
		}
		while(j>=0)
			A[k--] = B[j--];
    }
};