Relative Sort Array LeetCode
Two Approaches:
Explaination:::::::::::::::::::::::::::::::::::::
First, we will add all the elements of arr1 to the hashmap with the key as element and value as their frequency.
Second, we will traverse the arr2 as a take-up element one by one. If that element is present in the map (as a key) then we will take out frequency(ie. value) and store that element up to its frequency in the ArrayList(ac).
This ArrayList ac contains the relative order of elements that are duplicated (elements present in both arrays.)
Now for the remaining elements which are present in arr1 but not in arr2.
We will store the whole given array arr1 in an ArrayList aa and using the removeAll method ie by using aa.removeAll(ac) we will get aa without any duplicates.
By usage Of Collections. sort(aa) we will get the sorted ArrayList.
Now we will append both by using ac.addAll(aa).
And after converting ac to an array, we will return it.
The same thing we can do by using an additional LinkedHashSet which will store all the elements of arr2. And instead of applying for loop over arr2, we will use for(int a: set).
1. With Set
2. Without Set
That will be the only change in both approaches.
Approach 1:
Solution 1: Without Using Set
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ac=new ArrayList<Integer>();
for(int i=0;i<arr1.length;i++){
aa.add(arr1[i]);
}
//System.out.println("Full List is: "+aa);
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<arr1.length;i++){
if(map.containsKey(arr1[i])){
map.put(arr1[i],map.get(arr1[i])+1);
}
else{
map.put(arr1[i],1);
}
}
//map.forEach((k,v) -> System.out.println("Key is : "+k+" Value is : "+v));
for(int i=0;i<arr2.length;i++){
if(map.containsKey(arr2[i])){
for(int j=0;j<map.get(arr2[i]);j++){
ac.add(arr2[i]);
}
}
}
// System.out.println("DUpicates in sorted fashion: "+ac);
aa.removeAll(ac);
// System.out.println("Non-Dupli: "+aa);
Collections.sort(aa);
ac.addAll(aa);
//System.out.println("Final ArrayList is: "+ac);
int arr3[]=new int[ac.size()];
for(int i=0;i<ac.size();i++){
arr3[i]=ac.get(i);
}
return arr3;
TIME:O(N^2)[LeetCode Time: 5ms faster than 32.50% ]
SPACE:O(N)[LeetCode Memory: 39.1MB less than 60.16%]
***********************************************************************************
Approach 2:
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ac=new ArrayList<Integer>();
LinkedHashSet<Integer>set=new LinkedHashSet<Integer>();
for(int i=0;i<arr1.length;i++){
aa.add(arr1[i]);
}
//System.out.println("Full List is: "+aa);
for(int i=0;i<arr2.length;i++){
set.add(arr2[i]);
}
// System.out.println("Set is(Order to be Followed is): "+set);
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<arr1.length;i++){
if(map.containsKey(arr1[i])){
map.put(arr1[i],map.get(arr1[i])+1);
}
else{
map.put(arr1[i],1);
}
}
//map.forEach((k,v) -> System.out.println("Key is : "+k+" Value is : "+v));
for(int a:set){
if(map.containsKey(a)){
for(int i=0;i<map.get(a);i++){
ac.add(a);
}
}
}
// System.out.println("DUpicates in sorted fashion: "+ac);
aa.removeAll(ac);
// System.out.println("Non-Dupli: "+aa);
Collections.sort(aa);
ac.addAll(aa);
//System.out.println("Final ArrayList is: "+ac);
int arr3[]=new int[ac.size()];
for(int i=0;i<ac.size();i++){
arr3[i]=ac.get(i);
}
return arr3;
TIME:O(N^2)[LeetCode Time: 6ms faster than 23.87%]
SPACE:O(N)[LeetCode Memory: 39.4MB less than 32.90%]
Thanks For Reading😇.
"Share Further to Increase Knowledge Treasure😊".
Comments
Post a Comment