Dada una array arr[] que consta de N enteros, la tarea para cada elemento de la array es encontrar la diferencia absoluta entre el recuento de elementos distintos a la izquierda y a la derecha en la array dada arr[] .
Ejemplos:
Entrada: arr[] = {7, 7, 3, 2, 3}
Salida: 2 2 0 1 2
Explicación:
el número de elementos distintos que aparecen a la izquierda de cada índice está dado por [0, 0, 1, 1, 2] y el número de elementos distintos que aparecen a la derecha de cada índice es [2, 2, 1, 0, 0]. Tomando la diferencia absoluta de ambos se obtiene el resultado anterior.Entrada: arr[] = {4, 3, 2, 3}
Salida: 2 0 1 2
Enfoque ingenuo: el problema dado se puede resolver utilizando la estructura de datos establecida , la idea es iterar sobre el rango [0, i – 1] para encontrar el recuento de elementos distintos a la izquierda de cada elemento y, de manera similar, atravesar la array sobre el range [i + 1, N – 1] para encontrar los distintos elementos a la derecha de cada elemento. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array res[] que almacene la diferencia absoluta resultante de distintos elementos para cada elemento de la array.
- Recorra la array dada y para cada elemento en el índice realizo las siguientes operaciones:
- Itere sobre el rango [0, i – 1] e inserte todos los elementos en el conjunto, digamos S1 .
- Itere sobre el rango [i + 1, N – 1] e inserte todos los elementos en el conjunto, digamos S2 .
- Actualice el valor de res[i] como la diferencia absoluta de tamaños de los conjuntos S1 y S2 .
- Después de completar los pasos anteriores, imprima la array res[] como resultado.
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 difference of // count of distinct elements to the // left and right for each array elements void findDifferenceArray(int arr[], int N) { // Stores distinct array element // in the left and right set<int> S1; set<int> S2; // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.insert(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.insert(arr[j]); } // Print the difference cout << abs((int)S1.size() - (int)S2.size()) << ' '; S1.clear(); S2.clear(); } } // Driver Code int main() { int arr[] = { 7, 7, 3, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); findDifferenceArray(arr, N); return 0; }
Java
// Java program for the above approach import java.util.HashSet; class GFG{ // Function to find the difference of // count of distinct elements to the // left and right for each array elements public static void findDifferenceArray(int arr[], int N) { // Stores distinct array element // in the left and right HashSet<Integer> S1 = new HashSet<Integer>(); HashSet<Integer> S2 = new HashSet<Integer>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.add(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.add(arr[j]); } // Print the difference System.out.print(Math.abs(S1.size() - S2.size()) + " "); S1.clear(); S2.clear(); } } // Driver Code public static void main(String args[]) { int arr[] = { 7, 7, 3, 2, 3 }; int N = arr.length; findDifferenceArray(arr, N); } } // This code is contributed by gfgking.
Python3
# Python3 program for the above approach # Function to find the difference of # count of distinct elements to the # left and right for each array elements def findDifferenceArray(arr, N) : # Stores distinct array element # in the left and right S1 = set(); S2 = set(); # Traverse the array for i in range(N) : # Insert all element to the left # in the set S1 for j in range(i) : S1.add(arr[j]); # Insert all element to the right # in the set S2 for j in range(i + 1, N) : S2.add(arr[j]); # Print the difference print(abs(len(S1) - len(S2)),end=' '); S1.clear(); S2.clear(); # Driver Code if __name__ == "__main__" : arr = [ 7, 7, 3, 2, 3 ]; N = len(arr); findDifferenceArray(arr, N); # This code is contributed by AnkThon
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the difference of // count of distinct elements to the // left and right for each array elements public static void findDifferenceArray(int[] arr, int N) { // Stores distinct array element // in the left and right HashSet<int> S1 = new HashSet<int>(); HashSet<int> S2 = new HashSet<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (int j = 0; j < i; j++) { S1.Add(arr[j]); } // Insert all element to the right // in the set S2 for (int j = i + 1; j < N; j++) { S2.Add(arr[j]); } // Print the difference Console.Write(Math.Abs(S1.Count - S2.Count) + " "); S1.Clear(); S2.Clear(); } } // Driver code public static void Main(String[] args) { int[] arr = { 7, 7, 3, 2, 3 }; int N = arr.Length; findDifferenceArray(arr, N); } } // This code is contributed by sanjoy_62.
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the difference of // count of distinct elements to the // left and right for each array elements function findDifferenceArray(arr, N) { // Stores distinct array element // in the left and right let S1 = new Set(); let S2 = new Set(); // Traverse the array for (let i = 0; i < N; i++) { // Insert all element to the left // in the set S1 for (let j = 0; j < i; j++) { S1.add(arr[j]); } // Insert all element to the right // in the set S2 for (let j = i + 1; j < N; j++) { S2.add(arr[j]); } // Print the difference document.write(Math.abs(S1.size - S2.size) + ' '); S1.clear(); S2.clear(); } } // Driver Code let arr = [7, 7, 3, 2, 3]; let N = arr.length; findDifferenceArray(arr, N); // This code is contributed by Potta Lokesh </script>
3 1 1 1 3
Complejidad de Tiempo: O((N 2 )*log N)
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando la frecuencia de distintos elementos a la izquierda y a la derecha para cada elemento de la array y luego encontrar la diferencia resultante para cada elemento de la array. Siga los pasos a continuación para resolver el problema dado:
- Inicialice dos unordered_map leftMap y rightMap para almacenar los distintos elementos a la izquierda y derecha de cada índice, respectivamente.
- Recorra la array dada e inserte todos los elementos de la array en el mapa derecho .
- Recorra la array dada usando la variable i y realice los siguientes pasos:
- Cuente elementos distintos a la izquierda del elemento actual (digamos countLeft ) como el tamaño del mapa leftMap .
- Disminuya la frecuencia del elemento actual del mapa rightMap en 1 .
- Cuente elementos distintos a la derecha del elemento actual (digamos countRight ) como el tamaño del mapa rightMap .
- Incrementa la frecuencia del elemento actual en el mapa leftMap en 1 .
- Inserte el valor de la diferencia absoluta de tamaños de los mapas leftMap y rightMap .
- Después de completar los pasos anteriores, imprima la array res[] como resultado.
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 difference of // count of distinct elements to the // left and right for each array elements void findDifferenceArray(int arr[], int N) { // Stores the frequency of array // element to the left and the right unordered_map<int, int> leftMap, rightMap; // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { rightMap[arr[i]]++; } // Stores the resultant differences vector<int> res; // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.size(); // Decrement the frequency if (rightMap[arr[i]] > 1) { rightMap[arr[i]]--; } else { rightMap.erase(arr[i]); } // Find the count in the left int countRight = rightMap.size(); // Insert the resultant difference res.push_back(abs(countRight - countLeft)); // Increment the frequency leftMap[arr[i]]++; } // Print the result for (auto& it : res) { cout << it << ' '; } } // Driver Code int main() { int arr[] = { 7, 7, 3, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); findDifferenceArray(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the difference of // count of distinct elements to the // left and right for each array elements static void findDifferenceArray(int arr[], int N) { // Stores the frequency of array // element to the left and the right HashMap<Integer, Integer> leftMap = new HashMap<>(); HashMap<Integer, Integer> rightMap = new HashMap<>(); // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { if (rightMap.containsKey(arr[i])) rightMap.put(arr[i], rightMap.get(arr[i]) + 1); else rightMap.put(arr[i], 1); } // Stores the resultant differences Vector<Integer> res = new Vector<>(); // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.size(); // Decrement the frequency if (rightMap.get(arr[i]) > 1) { rightMap.put(arr[i], rightMap.get(arr[i]) - 1); } else { rightMap.remove(arr[i]); } // Find the count in the left int countRight = rightMap.size(); // Insert the resultant difference res.add(Math.abs(countRight - countLeft)); // Increment the frequency if (leftMap.containsKey(arr[i])) leftMap.put(arr[i], leftMap.get(arr[i]) + 1); else leftMap.put(arr[i], 1); } // Print the result for (int it : res) { System.out.print(it + " "); } } // Driver Code public static void main(String[] args) { int arr[] = { 7, 7, 3, 2, 3 }; int N = arr.length; findDifferenceArray(arr, N); } } // This code is contributed by Rajput-Ji
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the difference of // count of distinct elements to the // left and right for each array elements static void findDifferenceArray(int []arr, int N) { // Stores the frequency of array // element to the left and the right Dictionary<int, int> leftMap = new Dictionary<int, int>(); Dictionary<int, int> rightMap = new Dictionary<int, int>(); // Stores the frequency of array // element in the map rightMap for (int i = 0; i < N; i++) { if (rightMap.ContainsKey(arr[i])) rightMap[arr[i]] = rightMap[arr[i]] + 1; else rightMap.Add(arr[i], 1); } // Stores the resultant differences List<int> res = new List<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Find the count in the left int countLeft = leftMap.Count; // Decrement the frequency if (rightMap[arr[i]] > 1) { rightMap[arr[i]] = rightMap[arr[i]] - 1; } else { rightMap.Remove(arr[i]); } // Find the count in the left int countRight = rightMap.Count; // Insert the resultant difference res.Add(Math.Abs(countRight - countLeft)); // Increment the frequency if (leftMap.ContainsKey(arr[i])) leftMap[arr[i]]= leftMap[arr[i]] + 1; else leftMap.Add(arr[i], 1); } // Print the result foreach (int it in res) { Console.Write(it + " "); } } // Driver Code public static void Main(String[] args) { int []arr = { 7, 7, 3, 2, 3 }; int N = arr.Length; findDifferenceArray(arr, N); } } // This code is contributed by Rajput-Ji
3 1 1 1 3
Complejidad temporal: O(N) Espacio
auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por srijanbhardwaj52 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA