Find Median of two given Vectors
Given two vectors, a and b of different sizes, where array a has m number of elements and array b has n number of elements. The task is to find the median of two vectors. This problem is an extension of the Median of two sorted arrays of different sizes problem.
Example:
Input: a = {1, 4}
b = {2}Output: The median is 2.
Explanation:
The merged vector = {1, 2, 4}
So, the median is 2.Input: a = {1, 2}
b = {3, 5}Output: The median is 2.50000
Explanation:
The merged vector = {1, 2, 3, 5}
So, the median is (2 + 3) / 2 = 2.5.
Approach:
- Initialize vector a.
- Initialize vector b.
- Create a new vector of size a + b.
- Iterate using a loop the first vector and store the data into a newly created vector and similarly for the second vector after iterating the first vector.
- Merged both sorted vectors in the newly created vector by using the merge() STL function.
- Find the median for even and odd sizes and return it.
Below is the C++ implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the median double findMedianSortedVectors(vector< int >& a, vector< int >& b) { // New Vector of size a + b vector< int > c(a.size() + b.size()); int k = 0; double median = 0; int size_a = a.size(); int size_b = b.size(); for ( int i = 0; i < size_a; i++) { // Store data of first vector // in new vector c[k++] = a[i]; } for ( int i = 0; i < size_b; i++) { // Store second vector in // vector c c[k++] = b[i]; } merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // Merge the both sorted vectors int n = c.size(); if (n % 2 == 0) { // Calculate median for even // size vector median = c[(n / 2) - 1] + c[n / 2]; median = median / 2; } else { // Calculate median for odd // size vector median = c[(n - 1) / 2]; } return median; } // Driver code int main() { vector< int > v1; vector< int > v2; // Initialize first vector v1.push_back(1); v1.push_back(4); // Initialize second vector v2.push_back(2); // Invoke function to calculate // median double median_vectors = findMedianSortedVectors(v1, v2); // Print median value cout << median_vectors << endl; return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.Collections; import java.util.Vector; class GFG { public static double findMedianSortedVectors(Vector<Integer> a, Vector<Integer> b) { // New Vector of size a + b Vector<Integer> c = new Vector<Integer>(); double median = 0 ; int size_a = a.size(); int size_b = b.size(); for ( int i = 0 ; i < size_a; i++) { // Store data of first vector // in new vector c.add(a.get(i)); } for ( int i = 0 ; i < size_b; i++) { // Store second vector in // vector c c.add(b.get(i)); } // sort all the values Collections.sort(c); // Merge the both sorted vectors int n = c.size(); if (n % 2 == 0 ) { // Calculate median for even // size vector median = c.get((n / 2 ) - 1 ) + c.get(n / 2 ); median = median / 2 ; } else { // Calculate median for odd // size vector median = c.get((n - 1 ) / 2 ); } return median; } public static void main(String[] args) { Vector<Integer> v1 = new Vector<Integer>(); Vector<Integer> v2 = new Vector<Integer>(); // Initialize first vector v1.add( 1 ); v1.add( 4 ); // Initialize second vector v2.add( 2 ); // Invoke function to calculate // median double median_vectors = findMedianSortedVectors(v1, v2); // Print median value System.out.println(median_vectors); } } // This code is contributed by rj13to. |
Python3
# python program to implement # the above approach # Function to calculate the median def findMedianSortedVectors(a, b): # New list c = [] for i in range ( 0 , len (a)): c.append( 0 ) for i in range ( 0 , len (b)): c.append( 0 ) k = 0 median = 0 size_a = len (a) size_b = len (b) for i in range ( 0 , size_a): # Store data of first list # in new list c[k] = a[i] k + = 1 for i in range ( 0 , size_b): # Store second list in # c c[k] = b[i] k + = 1 # sort the new list c.sort() n = len (c) if (n % 2 = = 0 ): # Calculate median for even # size list median = c[(n / / 2 ) - 1 ] + c[n / / 2 ] median = median / 2 else : # Calculate median for odd # size list median = c[(n - 1 ) / / 2 ] return median # Driver Code # Initialize first list v1 = [ 1 , 4 ] # Initialize second list v2 = [ 2 ] # Invoke function to calculate # median median_lists = findMedianSortedVectors(v1, v2) # Print median value print (median_lists) # This code is contributed by rj13to. |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { public static double findMedianSortedVectors(ArrayList a, ArrayList b) { // New Vector of size a + b ArrayList c = new ArrayList(); double median = 0; int size_a = a.Count; int size_b = b.Count; for ( int i = 0; i < size_a; i++) { // Store data of first vector // in new vector c.Add(a[i]); } for ( int i = 0; i < size_b; i++) { // Store second vector in // vector c c.Add(b[i]); } // sort all the values c.Sort(); // Merge the both sorted vectors int n = c.Count; if (n % 2 == 0) { // Calculate median for even // size vector median = ( int )c[(n / 2) - 1] + ( int )c[n / 2]; median = median / 2; } else { // Calculate median for odd // size vector median = ( int )c[(n - 1) / 2]; } return median; } public static void Main() { ArrayList v1 = new ArrayList(); ArrayList v2 = new ArrayList(); // Initialize first vector v1.Add(1); v1.Add(4); // Initialize second vector v2.Add(2); // Invoke function to calculate // median double median_vectors = findMedianSortedVectors(v1, v2); // Print median value Console.WriteLine(median_vectors); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to calculate the median function findMedianSortedVectors(a, b) { // New Vector of size a + b let c = new Array(a.length + b.length); let k = 0; let median = 0; let size_a = a.length; let size_b = b.length; for (let i = 0; i < size_a; i++) { // Store data of first vector // in new vector c[k++] = a[i]; } for (let i = 0; i < size_b; i++) { // Store second vector in // vector c c[k++] = b[i]; } c.sort( function (a, b) { return a - b }) // Merge the both sorted vectors let n = c.length; if (n % 2 == 0) { // Calculate median for even // size vector median = c[(Math.floor(n / 2) - 1)] + c[(Math.floor(n / 2))]; median = Math.floor(median / 2); } else { // Calculate median for odd // size vector median = c[(Math.floor((n - 1) / 2))]; } return median; } // Driver code let v1 = []; let v2 = []; // Initialize first vector v1.push(1); v1.push(4); // Initialize second vector v2.push(2); // Invoke function to calculate // median let median_vectors = findMedianSortedVectors(v1, v2); // Print median value document.write(median_vectors + '<br>' ); // This code is contributed by Potta Lokesh </script> |
2
Complexity:
Time Complexity: O(m + n) as to merge both the vectors O(m+n) time is needed.
Space Complexity: O(1) as no extra space is required.