首页 > 代码库 > Leetcode:merge_sorted_array

Leetcode:merge_sorted_array

一、     题目

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

二、     分析

看到题目后感觉非常easy。就是比較两个数组中的元素嘛,可是刚開始发现假设合并到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--] ;
    }
};


 

Leetcode:merge_sorted_array