学步园

一、     题目

将给定的两个排好序的数组合并成一个有序数组。

二、     分析

看到题目后感觉很简单，就是比较两个数组中的元素嘛，但是刚开始发现如果合并到A[]中从前到后的话可能会导致原数据该，怎样才能避免这种错误呢？于是想到了逆向合并，从后往前填入数组。

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
    
    	int length=m+n-1;
    	m--;
    	n--;
        for(int i=length;i>=0;i--){
        	if (m == -1 || (n != -1 && A[m] <= B[n])) {  
                A[i] = B[n--];  
            }  
            else {  
                A[i] = A[m--];  
            }              
        }
    }
};


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