LeetCode题目:Merge Sorted Array

By | 2012 年 10 月 5 日

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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.



从大到小,选取两个数组末端大的那个数,放到A的末尾即可。



代码:24ms过大集合,时间复杂度是O(n)

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int last = m + n - 1;
        int lasta = m - 1;
        int lastb = n - 1;
        //select largest to right position
        while(lasta >= 0 && lastb >= 0) {
            A[last--] = (A[lasta] >= B[lastb] ? A[lasta--] : B[lastb--]);
        }
        //copy remain numbers in B to A
        for(int i = 0 ; i <= lastb; ++i)
            A[i] = B[i];
    }
};



Code rewrite at 2012-12-22

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int curi = m + n - 1;
        int ia = m - 1;
        int ib = n - 1;
        while(ia >= 0 && ib >= 0) {
            if(A[ia] >= B[ib]) {
                A[curi--] = A[ia--];
            } else {
                A[curi--] = B[ib--];
            }
        }
        while (ib >= 0) {
            A[curi--] = B[ib--];
        }
    }
};



Code rewrite at 2012-12-22, The simplest code

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ia = m - 1, ib = n - 1, icur = m + n - 1;
        while(ia >= 0 && ib >= 0) {
            A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
        }
        while(ib >= 0) {
            A[icur--] = B[ib--];
        }
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注