class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int x=0;
int y=0;
int n=nums1.length;
int m=nums2.length;
PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
while(x<nums1.length && y<nums2.length){
if(nums1[x]<nums2[y]){
pq.add(nums1[x]);
x++;
}
else if(nums1[x]>nums2[y]){
pq.add(nums2[y]);
y++;
}
else{
pq.add(nums1[x]);
pq.add(nums2[y]);
x++;
y++;
}
}
for(;x<n;x++){
pq.add(nums1[x]);
}
for(;y<m;y++){
pq.add(nums2[y]);
}
ArrayList<Integer>aa=new ArrayList<Integer>();
aa.addAll(pq);
int a=aa.size();
double median=0.0;
if((a/2)*2==a){
int b=a/2;
int val3=aa.get(b-1)+aa.get(b);
median=(val3/(double)2);
}
else{
int b=a/2;
median=(double)aa.get(b);
}
return median;
}
}
Approach:
Here we will traverse both the list together and see for smaller element in both lists and simultaneously add it to the priority queue. Value for the pointer will be increased for the list whose elements get add up in the queue. If the same value elements are there then the value for both pointers will be increased simultaneously and both elements will be added to the queue.
After that, if any list elements are untraversed we will add those elements to the queue.
Here priority queue will remove elements in decreasing order of their priority. So we will first get the minimum value element and then the large value elements, following the natural ordering of the priority queue.
Now for getting elements by indexing so as to find the median we will convert the queue into ArrayList.
Then look for size if the size is even then found the median by an average of two mid values else directly the mid index value will be median.
Time: O((n+m)*log(n+m)) [Priority Queue.][LeetCode Time : 5ms less than 23.58%] [Geeks for Geeks Time: 1.6/2.8]
Space: O(n+m)[ArrayList and Priority Queue occupy some space][LeetCode Memory: 39.9 MB less than 95.34%]
"Thanks for Reading 😇."
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment