LeetCode 88 — Merge Sorted Array（C++ Java Python）

题目： http://oj.leetcode.com/problems/merge-sorted-array/

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.

题目翻译：

给定两个有序整数数组A和B，把B并入A成为一个有序数组。
注意：
可以假设A有足够的空间（大小大于等于m + n）来保存来自B的额外元素。A和B的初始元素个数分别为m和n。

分析：
        从后向前考虑。如果A中的先遍历完，应把B中剩下的元素复制到A中。
C++实现：

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
    	if(n == 0)
    	{
    		return;
    	}

    	int idx = m + n - 1;
    	int i = m - 1;
    	int j = n - 1;

    	while(i >= 0 && j >= 0)
    	{
    		if(A[i] >= B[j])
    		{
    			A[idx--] = A[i--];
    		}
    		else
    		{
    			A[idx--] = B[j--];
    		}
    	}

    	if(i == -1)
    	{
    		while(j >= 0)
    		{
    			A[j] = B[j];
    			j--;
    		}
    	}
    }
};

Java实现：

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
		int idx = m + n - 1;
		int i = m - 1;
		int j = n - 1;

		while (i >= 0 && j >= 0) {
			if (A[i] >= B[j]) {
				A[idx--] = A[i--];
			} else {
				A[idx--] = B[j--];
			}
		}

		if (i == -1) {
			while (j >= 0) {
				A[j] = B[j];
				j--;
			}
		}
    }
}

Python实现：

class Solution:
    # @param A  a list of integers
    # @param m  an integer, length of A
    # @param B  a list of integers
    # @param n  an integer, length of B
    # @return nothing
    def merge(self, A, m, B, n):
        idx = m + n - 1
        i = m - 1
        j = n - 1
        
        while i >= 0 and j >= 0:
            if A[i] >= B[j]:
                A[idx] = A[i]
                i -= 1
            else:
                A[idx] = B[j]
                j -= 1
            
            idx -= 1
        
        if i == -1:
            while j >= 0:
                A[j] = B[j]
                j -= 1

        感谢阅读，欢迎评论！