Dadas dos arrays arr1[] y arr2[] . La array arr1[] está ordenada. La tarea es imprimir el cambio en la mediana después de eliminar cada elemento de la array arr2[] uno por uno.
Nota: La array arr2[] tiene solo aquellos elementos que están presentes en la array arr1[] .
Ejemplos:
Entrada: arr1[] = {2, 4, 6, 8, 10}, arr2[] = {4, 6}
Salida: 1 1
Explicación:
Inicialmente, la mediana es 6.
Después de eliminar 4, la array se convierte en arr1[] = {2 , 6, 8, 10}, mediana = 7, por lo tanto, la diferencia es 7 – 6 = 1.
Después de quitar 6, la array se convierte en arr1[] = {2, 8, 10}, mediana = 8, por lo tanto, la diferencia es 8 – 7 = 1.Entrada: arr1[] = {1, 100, 250, 251}, arr2[] = {250, 1}
Salida: -75 75.5
Explicación:
Inicialmente, la mediana es 175.
Después de eliminar 250, la array se convierte en arr1[] = {1, 100, 251}, mediana = 100, por lo tanto la diferencia es 100 – 175 = -75.
Después de eliminar 1, la array se convierte en arr1[] = {100, 251}, mediana = 175,5, por lo que la diferencia es 175,5 – 100 = 75,5.
Enfoque: la idea es atravesar cada elemento de la array arr2[] y eliminar cada elemento de la array arr1[] y almacenar la mediana de la array arr1[] después de cada eliminación de elementos en una array (digamos temp[] ). Imprima la diferencia consecutiva de los elementos de la array para obtener el cambio en la mediana después de eliminar elementos de arr2[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the median change
// after removing elements from arr2[]
void medianChange(vector<int>& arr1,
vector<int>& arr2)
{
int N = arr1.size();
// To store the median
vector<float> median;
// Store the current median
// If N is odd
if (N & 1) {
median
.push_back(arr1[N / 2] * 1.0);
}
// If N is even
else {
median
.push_back((arr1[N / 2]
+ arr1[(N - 1) / 2])
/ 2.0);
}
for (auto& x : arr2) {
// Find the current element
// in arr1
auto it = find(arr1.begin(),
arr1.end(),
x);
// Erase the element
arr1.erase(it);
// Decrement N
N--;
// Find the new median
// and append
// If N is odd
if (N & 1) {
median
.push_back(arr1[N / 2] * 1.0);
}
// If N is even
else {
median
.push_back((arr1[N / 2]
+ arr1[(N - 1) / 2])
/ 2.0);
}
}
// Print the corresponding
// difference of median
for (int i = 0;
i < median.size() - 1;
i++) {
cout << median[i + 1] - median[i]
<< ' ';
}
}
// Driven Code
int main()
{
// Given arrays
vector<int> arr1 = { 2, 4, 6, 8, 10 };
vector<int> arr2 = { 4, 6 };
// Function Call
medianChange(arr1, arr2);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to find the median
// change after removing elements
// from arr2[]
public static void medianChange(List<Integer> arr1,
List<Integer> arr2)
{
int N = arr1.size();
// To store the median
List<Integer> median = new ArrayList<>();
// Store the current median
// If N is odd
if ((N & 1) != 0)
median.add(arr1.get(N / 2) * 1);
// If N is even
else
median.add((arr1.get(N / 2) +
arr1.get((N - 1) / 2)) / 2);
for(int x = 0; x < arr2.size(); x++)
{
// Find the current element
// in arr1
int it = arr1.indexOf(arr2.get(x));
// Erase the element
arr1.remove(it);
// Decrement N
N--;
// Find the new median
// and append
// If N is odd
if ((N & 1) != 0)
{
median.add(arr1.get(N / 2) * 1);
}
// If N is even
else
{
median.add((arr1.get(N / 2) +
arr1.get((N - 1) / 2)) / 2);
}
}
// Print the corresponding
// difference of median
for(int i = 0; i < median.size() - 1; i++)
{
System.out.print(median.get(i + 1) -
median.get(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
List<Integer> arr1 = new ArrayList<Integer>(){
{ add(2); add(4); add(6); add(8); add(10); } };
List<Integer> arr2 = new ArrayList<Integer>(){
{ add(4); add(6); } };
// Function Call
medianChange(arr1, arr2);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program for the # above approach # Function to find the median # change after removing elements # from arr2[] def medianChange(arr1, arr2): N = len(arr1) # To store the median median = [] # Store the current median # If N is odd if (N & 1): median.append(arr1[N // 2] * 1) # If N is even else: median.append((arr1[N // 2] + arr1[(N - 1) // 2]) // 2) for x in arr2: # Find the current # element in arr1 it = arr1.index(x) # Erase the element arr1.pop(it) # Decrement N N -= 1 # Find the new median # and append # If N is odd if (N & 1): median.append(arr1[N // 2] * 1) # If N is even else: median.append((arr1[N // 2] + arr1[(N - 1) // 2]) // 2) # Print the corresponding # difference of median for i in range(len(median) - 1): print(median[i + 1] - median[i], end = ' ') # Driver Code if __name__ == "__main__": # Given arrays arr1 = [2, 4, 6, 8, 10] arr2 = [4, 6] # Function Call medianChange(arr1, arr2) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the median change
// after removing elements from arr2[]
static void medianChange(List<int> arr1,
List<int> arr2)
{
int N = arr1.Count;
// To store the median
List<double> median = new List<double>();
// Store the current median
// If N is odd
if ((N & 1) != 0)
{
median.Add(arr1[N / 2] * 1.0);
}
// If N is even
else
{
median.Add((arr1[N / 2] +
arr1[(N - 1) / 2]) / 2.0);
}
foreach(int x in arr2)
{
// Find the current element
// in arr1
int it = arr1.IndexOf(x);
// Erase the element
arr1.RemoveAt(it);
// Decrement N
N--;
// Find the new median
// and append
// If N is odd
if ((N & 1) != 0)
{
median.Add(arr1[N / 2] * 1.0);
}
// If N is even
else
{
median.Add((arr1[N / 2] +
arr1[(N - 1) / 2]) / 2.0);
}
}
// Print the corresponding
// difference of median
for(int i = 0; i < median.Count - 1; i++)
{
Console.Write(median[i + 1] -
median[i] + " ");
}
}
// Driver Code
static void Main()
{
// Given arrays
List<int> arr1 = new List<int>(
new int[]{ 2, 4, 6, 8, 10 });
List<int> arr2 = new List<int>(
new int[]{ 4, 6 });
// Function Call
medianChange(arr1, arr2);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program for the
// above approach
// Function to find the median
// change after removing elements
// from arr2[]
function medianChange(arr1,arr2)
{
let N = arr1.length;
// To store the median
let median = [];
// Store the current median
// If N is odd
if ((N & 1))
median.push((arr1[Math.floor(N / 2)] * 1));
// If N is even
else
median.push(Math.floor((arr1[Math.floor(N / 2)] +
arr1[Math.floor((N - 1) / 2)]) / 2));
for(let x = 0; x < arr2.length; x++)
{
// Find the current element
// in arr1
let it = arr1.indexOf(arr2[x]);
// Erase the element
arr1.splice(it,1);
// Decrement N
N--;
// Find the new median
// and append
// If N is odd
if ((N & 1))
{
median.push(arr1[Math.floor(N / 2)] * 1);
}
// If N is even
else
{
median.push(Math.floor((arr1[Math.floor(N / 2)] +
arr1[Math.floor((N - 1) / 2)]) / 2));
}
}
// Print the corresponding
// difference of median
for(let i = 0; i < median.length - 1; i++)
{
document.write((median[i + 1] -
median[i]) + " ");
}
}
// Driver Code
// Given arrays
let arr1 = [2, 4, 6,
8, 10];
let arr2 = [4, 6];
// Function Call
medianChange(arr1, arr2)
// This code is contributed by avanitrachhadiya2155
</script>
1 1
Complejidad temporal: O(M*N)
Espacio auxiliar : O(M * N)
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA