HashMap/HashSet are an alternative for unodered map in c++
Recently I came across a problem in which I needed to have linear time complexity while finding the union of two array.
It was possible to do it for sorted array , but in an unsorted array , the process of sorting itself takes o(n²) complexity :
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Arrays;class GFG {
public static void main (String[] args) {
//code
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0)
{
int n = sc.nextInt();
int m = sc.nextInt();
int a[] = new int[n];
int b[] = new int[m];
for(int i=0;i<n;i++)
{
a[i] = sc.nextInt();
}
for(int i=0;i<m;i++)
{
b[i] = sc.nextInt();
}
Arrays.sort(a, 0, n);
Arrays.sort(b, 0, m);
int nn= n;
// i am assuming that both the arrays are sorted
int l;
if(n<=m){
l=n;
}
else{
l=m;
}
int arr[] = new int[l];
int pa=0 , pb=0 , pl=0 , c=0;
while(pa <n &&pb <m)
{
if(a[pa]== b[pb])
{
arr[pl] = a[pa];
pl++;
pa++;
pb++;
c++;
}
else if(a[pa]<b[pb])
{
pa++;
}
else if(a[pa]>b[pb])
{
pb++;
}
}
//done with entering no. in array
System.out.println(c);
t — ;
}
}
}
so to tackle this issue(according to a solution I found online) , instead of performing sorting we can use unordered map for using the number as a key .
similarly in hashmap we can insert key value pairs to solve this problem.
Hashmap are classes that implement map interface(map interface extends collection).
import java.util.HashMap; // import the HashMap class
HashMap<Integer, Integer> union = new HashMap<Integer, Integer>();
so , we can run a loop through both the arrays and store the numbers inside them in union as as unique keys . and now to get the union of two arrays we can just get the key set of union .
but for my implementation it was observered that HashSet was more useful as their was no need of the value part in the collection.so I used hashset instead to store the unique elements of both array and the used size() to find out the count of the union of both the array.
import java.util.*;
import java.lang.*;
import java.io.*;class GFG {
public static void main (String[] args) {
//code
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0)
{
int n = sc.nextInt();
int m = sc.nextInt();
int a[] = new int[n];
int b[] = new int[m];
for(int i=0;i<n;i++)
{
a[i] = sc.nextInt();
}
for(int i=0;i<m;i++)
{
b[i] = sc.nextInt();
}
//done with entering no. in arrayHashSet<Integer> union = new HashSet<Integer>();
for(int i=0;i<n;i++)
{
int key = a[i] ;
union.add(key);
}
for(int i=0;i<m;i++)
{
int key = b[i] ;
union.add(key);
}
//all the unique nos. are present in the hashset union.
System.out.println(union.size());t — ;
}
}
}
So this was my approach which took 2.10 sec . Thank You!