Изменение медианы данного массива после удаления данных элементов
Даны два массива arr1 [] и arr2 [] . Массив arr1 [] отсортирован. Задача состоит в том, чтобы распечатать изменение медианы после удаления каждого элемента из массива arr2 [] по одному.
Примечание. В массиве arr2 [] есть только те элементы, которые присутствуют в массиве arr1 [] .
Примеры:
Input: arr1[] = {2, 4, 6, 8, 10}, arr2[] = {4, 6}
Output: 1 1
Explanation:
Initially median is 6.
After removing 4, array becomes arr1[] = {2, 6, 8, 10}, median = 7, therefore the difference is 7 – 6 = 1.
After removing 6, array becomes arr1[] = {2, 8, 10}, median = 8, therefore the difference is 8 – 7 = 1.Input: arr1[] = {1, 100, 250, 251}, arr2[] = {250, 1}
Output: -75 75.5
Explanation:
Initially median is 175.
After removing 250, array becomes arr1[] = {1, 100, 251}, median = 100, therefore the difference is 100 – 175 = -75.
After removing 1, array becomes arr1[] = {100, 251}, median = 175.5, therefore the difference is 175.5 – 100 = 75.5.
Подход: идея состоит в том, чтобы пройти каждый элемент массива arr2 [] и удалить каждый элемент из массива arr1 [] и сохранить медиану массива arr1 [] после каждого удаления элемента в массиве (скажем, temp [] ). Выведите последовательную разность элементов массива, чтобы получить изменение медианы после удаления элементов из arr2 [] .
Ниже представлена реализация описанного выше подхода:
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 Codeint main(){ // Given arrays vector< int > arr1 = { 2, 4, 6, 8, 10 }; vector< int > arr2 = { 4, 6 }; // Function Call medianChange(arr1, arr2); return 0;} |
Джава
// Java program for the// above approachimport 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 Codepublic 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 Codeif __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 approachusing 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 Codestatic 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 |
1 1
Сложность времени: O (M * N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.