码疯窝

LeetCode 每日一题 — Merge Sorted Array

2015/01/07 10:32:34    分类: 日志连载    0人评论 次浏览

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 n respectively.

算法分析: 这个貌似是归并算法的一部分. 给A, B分别分配个指针, 比较A[i]和B[j], 或A小, 则A指针右移, 反之, 把A[i]后面的所有数据全体后移一位, 空出一位插入B[j]. 若A先扫描完, B未扫描完, 说明B里面剩下的数据都大于A, 直接放入A尾部.

Java:

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

C++:

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < m && j < n) {
            if (A[i] >= B[j]) {
                k = m;
                m++;
                while(k > i) {
                    A[k] = A[k - 1];
                    k--;
                }
                A[i] = B[j];
                i++;
                j++;
            } else 
                i++;
        }
        if (j != n) {
            while (j < n) {
                A[i] = B[j];
                i++;
                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):
        i = 0
        j = 0
        k = 0
        while(i < m and j < n):
            if (A[i] >= B[j]):
                k = m
                m += 1
                while(k > i):
                    A[k] = A[k - 1]
                    k -= 1
                A[i] = B[j]
                i += 1
                j += 1
            else:
                i += 1
        if (j != n):
            while(j < n):
                A[i] = B[j]
                j += 1
                i += 1
继续查看有关 日志连载的文章

0个访客评论