merge two sorted arrays
merge two sorted arrays \( a \) and \( b \) while removing duplicates is to use
the two-pointer technique.
```java
import java.util.ArrayList;
public class GFG {
public static void main(String[] args) {
int[] a = {1, 3, 5, 7};
int[] b = {2, 4, 6, 8};
ArrayList<Integer> mergedArray = new ArrayList<>();
int i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
if (mergedArray.isEmpty() || mergedArray.get(mergedArray.size() -
1) != a[i]) {
mergedArray.add(a[i]);
}
i++;
} else if (b[j] < a[i]) {
if (mergedArray.isEmpty() || mergedArray.get(mergedArray.size() -
1) != b[j]) {
mergedArray.add(b[j]);
}
j++;
} else {
if (mergedArray.isEmpty() || mergedArray.get(mergedArray.size() -
1) != a[i]) {
mergedArray.add(a[i]);
}
i++;
j++;
}
}
while (i < a.length) {
if (mergedArray.isEmpty() || mergedArray.get(mergedArray.size() - 1) !=
a[i]) {
mergedArray.add(a[i]);
}
i++;
}
while (j < b.length) {
if (mergedArray.isEmpty() || mergedArray.get(mergedArray.size() - 1) !=
b[j]) {
mergedArray.add(b[j]);
}
j++;
}
System.out.println(mergedArray);
}
}
```
### Time Complexity Analysis:
1. The while-loop for merging the arrays takes \( O(n + m) \) time, where \( n \)
and \( m \) are the lengths of arrays \( a \) and \( b \) respectively.
So, the overall time complexity is \( O(n + m) \).
### Space Complexity:
The space complexity is \( O(n + m) \) due to the ArrayList `mergedArray` used for
storing the merged elements.
### Why This Approach?
This approach is more efficient than using a TreeMap because it takes linear time
and does not involve any logarithmic factors. It also uses less memory as there's
no need for an additional data structure to store the frequency or sorting status
of elements. The two-pointer technique is a commonly used method for solving
problems involving sorted arrays, and it works well in this case.
###########################################################################
Using Maps
Insert elements of both arrays in a map as keys.
Print the keys of the map.
(O(nlog(n) + mlog(m)
space O(N)
// Java program to merge two sorted arrays
//using maps
import java.io.*;
import java.util.*;
class GFG {
// Function to merge arrays
static void mergeArrays(int a[], int b[], int n, int m)
{
// Declaring a map.
// using map as a inbuilt tool
// to store elements in sorted order.
Map<Integer,Boolean> mp = new TreeMap<Integer,Boolean>();
// Inserting values to a map.
for(int i = 0; i < n; i++)
{
mp.put(a[i], true);
}
for(int i = 0;i < m;i++)
{
mp.put(b[i], true);
}
// Printing keys of the map.
for (Map.Entry<Integer,Boolean> me : mp.entrySet())
{
System.out.print(me.getKey() + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int a[] = {1, 3, 5, 7}, b[] = {2, 4, 6, 8};
int size = a.length;
int size1 = b.length;
// Function call
mergeArrays(a, b, size, size1);
}
}
