[closed] Merge Sorted Array

Question

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.

Answer 1

6

public class Solution {

public void merge(int A[], int m, int B[], int n) {

    while(n>0){
        if(m <=0 || A[m-1] < B[n-1])
            A[n+m-1] = B[--n];
        else
            A[n+m-1] = A[--m];
    }
}

}

link

answered 17 Jan, 13:10

nipoleon
61●1●3
accept rate: 0%

edited 17 Jan, 13:10

void merge(int A[], int m, int B[], int n) {
    while(n>0){
        if(m>0 && A[m-1]>B[n-1]){
            A[n+m-1]=A[m-1];
            m--;
        }else{
            A[n+m-1]=B[n-1];
            n--;
        }
    }
}

This version is a litter longer , used more words, but more clear. Cause the ambiguous --m is replaced.
A[n+m-1]=A[--m] is more likely to be interpreted as
two sentences
--m;
A[n+m-1]=A[m];

(26 Sep, 04:05) c0mm3t

Answer 2

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

Answer 3

public void merge(int A[], int m, int B[], int n) {
    m--;
    n--;
    for (int i = A.length - 1; i >= 0; i--) {
        if (m >= 0 && n >= 0) {
            if (A[m] > B[n]) {
                A[i] = A[m--];
            } else {
                A[i] = B[n--];
            }
        } else if (m >= 0) {
            A[i] = A[m--];
        } else {
            A[i] = B[n--];
        }
    }
}

Answer 4

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

Answer 5

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
if (n==0)
    return;
int mergePos = m + n - 1;
int i = m - 1;
int j = n - 1;
while (i>=0 && j>=0)
{
    if (A[i] > B[j])
        A[mergePos--] = A[i--];
    else
        A[mergePos--] = B[j--];
}
while (i>=0)
    A[mergePos--] = A[i--];
while (j>=0)
    A[mergePos--] = B[j--];
}
};

Answer 6

    int j = m + n -1;
    while( m!= 0 && n != 0)
    {
        if( A[m-1] < B[n-1])
        {
            A[j] = B[n-1];
            j--;
            n--;
        } 
        else
        {
            A[j] = A[m-1];
            j--;
            m--;
        }
    }
    while( m != 0)
    {
        A[j] = A[m-1];
        j--;
        m--;
    }
    while( n != 0)
    {
        A[j] = B[n-1];
        j--;
        n--;
    }

Answer 7

void merge(int A[], int m, int B[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int last = m+n-1;
    int i=m-1, j=n-1;
    while (i>=0 && j>=0) {

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

Answer 8

/*
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.
*/

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

//Do it backward
void MergeSortedArray(int *A, int m, int *B, int n){
    int posA = m - 1, posB = n - 1, pos = m + n - 1, swap = 0;
    for (; pos >= 0; --pos){
        if (A[posA] > B[posB]){
            A[pos] = A[posA];
            posA--;
        }
        else if (A[posA] < B[posB]){
            A[pos] = B[posB];
            posB--;
        }
        else{
            A[pos] = A[--pos] = A[posA];
            posA--; posB--;
        }
    }
}

//Do it in-place
int main(){
    int A[20] = {1,3,5,6,12,13,15,16,27,32};
    int B[5]  = {2,8,14,24,44};
    MergeSortedArray(A, 10, B, 5);
    for (int i = 0; i < (15); ++i){
        cout << A[i] << ' ';
    }
    cout << endl;
    return 0;
}

Answer 9

void merge(int A[], int m, int B[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int a, b;
    for (a = m-1, b = n-1; a >= 0 && b >= 0;) {
        if (A[a] >= B[b]) {
            A[a+b+1] = A[a];
            a--;
        } else {
            A[a+b+1] = B[b];
            b--;
        }
    }

    if (b >= 0) {
        for (int i = 0; i <= b; i++) {
            A[i] = B[i];
        }
    }
}

Answer 10

public class Solution { public void merge(int A[], int m, int B[], int n) {

    int posA = m-1, posB = n-1;
    boolean selectA;
    for(int i = m+n-1;i>=0;i--){
    if(posB<0||posA < 0)   selectA = (posB < 0)          ? true:false;
    else                   selectA = (A[posA] > B[posB]) ? true:false;         
    A[i] = selectA ? A[posA] : B[posB];
    posA = selectA ? posA-1  : posA;
    posB = selectA ? posB    : posB-1;
    }

}

[closed] Merge Sorted Array

The question has been closed for the following reason "bulk close" by 1337c0d3r 25 Oct, 06:41

Follow this question

Welcome to LeetCode

Related questions