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>
Producción:
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
Producción:
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