Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note: You have to modify the array A to contain the merge of A and B. Do not output anything in your code. TIP: C users, please malloc the result into a new array and return the result.
If the number of elements initialized in A and B are m and n respectively, the resulting size of array A after your code is executed should be m + n
Example :
Input :
A : [1 5 8]
B : [6 9]
Modified A : [1 5 6 8 9]
Method 1:
Sort
Solution:
Time: O(nlogn) Space: O(1)
public class Solution { public void merge(ArrayList<Integer> a, ArrayList<Integer> b) { a.addAll(b); Collections.sort(a); } }
Method 2:
Allocate a first, and then fill it from the end.
Solution:
Time: O(n) Space: O(1)
public class Solution { public void merge(ArrayList<Integer> a, ArrayList<Integer> b) { int aSize = a.size(); for (int i = 0; i < b.size(); i ++) { a.add(0); } int i = aSize - 1; int j = b.size() - 1; int p = a.size() - 1; while (i >= 0 && j >= 0) { int aVal = a.get(i); int bVal = b.get(j); if (aVal > bVal) { a.set(p, aVal); i --; } else { a.set(p, bVal); j --; } p --; } while (i >= 0) { a.set(p--, a.get(i--)); } while (j >= 0) { a.set(p--, b.get(j --)); } } }