Encuentra la mediana de dos vectores dados

Dados dos vectores, a y b de diferentes tamaños, donde el arreglo a tiene m número de elementos y el arreglo b tiene n número de elementos. La tarea es encontrar la mediana de dos vectores. Este problema es una extensión del problema de la Mediana de dos arrays ordenadas de diferentes tamaños . 

Ejemplo:

Entrada: a = {1, 4}
          b = {2}

Salida: La mediana es 2.

Explicación: 
El vector fusionado = {1, 2, 4} 
Entonces, la mediana es 2.

Entrada: a = {1, 2}
           b = {3, 5}

Salida: La mediana es 2.50000

Explicación: 
El vector fusionado = {1, 2, 3, 5} 
Entonces, la mediana es (2 + 3) / 2 = 2.5.

Acercarse:

1. Inicializa el vector a.
2. Inicializar el vector b.
3. Cree un nuevo vector de tamaño a + b .
4. Itere usando un ciclo el primer vector y almacene los datos en un vector recién creado y de manera similar para el segundo vector después de iterar el primer vector.
5. Fusionó ambos vectores ordenados en el vector recién creado usando la función merge() STL.
6. Encuentra la mediana para los tamaños pares e impares y devuélvela.

A continuación se muestra la implementación en C++ del enfoque anterior:

// 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 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.

# 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# 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.

<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

Complejidad:

Complejidad de tiempo: O(m + n) ya que para fusionar ambos vectores O(m+n) se necesita tiempo.
Complejidad espacial: O(1) ya que no se requiere espacio extra.