Dada una array , arr[] que consta de N enteros, la tarea para cada elemento de la array arr[i] es imprimir la suma de |i – j| para todos los posibles índices j tales que arr[i] = arr[j] .
Ejemplos:
Entrada: arr[] = {1, 3, 1, 1, 2}
Salida: 5 0 3 4 0
Explicación:
Para arr[0], sum = |0 – 0| + |0 – 2| + |0 – 3| = 5.
Para arr[1], suma = |1 – 1| = 0.
Para arr[2], suma = |2 – 0| + |2 – 2| + |2 – 3| = 3.
Para arr[3], suma = |3 – 0| + |3 – 2| + |3 – 3| = 4.
Para arr[4], suma = |4 – 4| = 0.
Por lo tanto, la salida requerida es 5 0 3 4 0.Entrada: arr[] = {1, 1, 1}
Salida: 3 2 3
Enfoque ingenuo: consulte la publicación anterior de este artículo para conocer el enfoque más simple para resolver el problema.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque basado en mapas : consulte la publicación anterior de este artículo para resolver el problema con Map .
Complejidad temporal: O(N*L)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando el índice anterior y el recuento de ocurrencias de cada elemento en un HashMap . Siga los pasos a continuación para resolver el problema:
- Inicialice un HashMap , diga M para almacenar arr[i] como clave y (recuento, índice anterior) como valor.
- Inicialice dos arrays L[] y R[] de tamaño N donde L[i] denota la suma de |i – j| para todos los índices posibles j < i y arr[i] = arr[j] y R[i] denota la suma de |i – j| para todos los índices posibles j > i y arr[i] = arr[j] .
- Recorra la array dada arr[] sobre el rango [0, N – 1] y realice los siguientes pasos:
- Si arr[i] está presente en el mapa M , actualice el valor de L[i] a 0 y M[arr[i]] para almacenar el par {1, i} donde el primer elemento denota el recuento de ocurrencias y el segundo elemento denota el índice anterior del elemento.
- De lo contrario, encuentre el valor de arr[i] del mapa M y almacene el conteo y el índice anterior en las variables cnt y j respectivamente.
- Actualice el valor de L[i] a (cnt * (i – j) + L[j]) y el valor de arr[i] en M para almacenar el par (cnt + 1, i) .
- Repita el mismo proceso para actualizar los valores en la array R[] .
- Iterar sobre el rango [0, N – 1] usando la variable i e imprimir el valor (L[i] + R[i]) 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;
// Stores the count of occurrences
// and previous index of every element
struct pairr
{
int count, prevIndex;
// Constructor
pairr(int count, int prevIndexx)
{
count = count;
prevIndex = prevIndexx;
}
};
// Function to calculate the sum of
// absolute differences of indices
// of occurrences of array element
void findSum(int arr[], int n)
{
// Stores the count of elements
// and their previous indices
map<int, pairr*> mapp;
// Initialize 2 arrays left[]
// and right[] of size N
int left[n];
int right[n];
// Traverse the given array
for(int i = 0; i < n; i++)
{
// If arr[i] is present in the Map
if (mapp.find(arr[i]) == mapp.end())
{
// Update left[i] to 0
// and update the value
// of arr[i] in map
left[i] = 0;
mapp[arr[i]] = new pairr(1, i);
}
// Otherwise, get the value from
// the map and update left[i]
else
{
pairr* tmp = mapp[arr[i]];
left[i] = (tmp->count) * (i - tmp->prevIndex) +
left[tmp->prevIndex];
mapp[arr[i]] = new pairr(tmp->count + 1, i);
}
}
// Clear the map to calculate right[] array
mapp.clear();
// Traverse the array arr[] in reverse
for(int i = n - 1; i >= 0; i--)
{
// If arr[i] is present in theMap
if (mapp.find(arr[i]) == mapp.end())
{
// Update right[i] to 0
// and update the value
// of arr[i] in the Map
right[i] = 0;
mapp[arr[i]] = new pairr(1, i);
}
// Otherwise get the value from
// the map and update right[i]
else
{
pairr* tmp = mapp[arr[i]];
right[i] = (tmp->count) *
(abs(i - tmp->prevIndex)) +
right[tmp->prevIndex];
mapp[arr[i]] = new pairr(tmp->count + 1, i);
}
}
// Iterate in the range [0, N-1]
// and print the sum of left[i]
// and right[i] as the result
for(int i = 0; i < n; i++)
cout << left[i] + right[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 1, 1, 2 };
int N = 5;
findSum(arr, N);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Stores the count of occurrences
// and previous index of every element
static class pair {
int count, prevIndex;
// Constructor
pair(int count, int prevIndex)
{
this.count = count;
this.prevIndex = prevIndex;
}
}
// Function to calculate the sum of
// absolute differences of indices
// of occurrences of array element
static void findSum(int[] arr, int n)
{
// Stores the count of elements
// and their previous indices
Map<Integer, pair> map = new HashMap<>();
// Initialize 2 arrays left[]
// and right[] of size N
int[] left = new int[n];
int[] right = new int[n];
// Traverse the given array
for (int i = 0; i < n; i++) {
// If arr[i] is present in the Map
if (!map.containsKey(arr[i])) {
// Update left[i] to 0
// and update the value
// of arr[i] in map
left[i] = 0;
map.put(arr[i], new pair(1, i));
}
// Otherwise, get the value from
// the map and update left[i]
else {
pair tmp = map.get(arr[i]);
left[i] = (tmp.count)
* (i - tmp.prevIndex)
+ left[tmp.prevIndex];
map.put(
arr[i], new pair(
tmp.count + 1, i));
}
}
// Clear the map to calculate right[] array
map.clear();
// Traverse the array arr[] in reverse
for (int i = n - 1; i >= 0; i--) {
// If arr[i] is present in theMap
if (!map.containsKey(arr[i])) {
// Update right[i] to 0
// and update the value
// of arr[i] in the Map
right[i] = 0;
map.put(arr[i], new pair(1, i));
}
// Otherwise get the value from
// the map and update right[i]
else {
pair tmp = map.get(arr[i]);
right[i]
= (tmp.count)
* (Math.abs(i - tmp.prevIndex))
+ right[tmp.prevIndex];
map.put(
arr[i], new pair(
tmp.count + 1, i));
}
}
// Iterate in the range [0, N-1]
// and print the sum of left[i]
// and right[i] as the result
for (int i = 0; i < n; i++)
System.out.print(
left[i] + right[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 1, 1, 2 };
int N = arr.length;
findSum(arr, N);
}
}
Python3
# Python program for the above approach
# Stores the count of occurrences
# and previous index of every element
class pair:
def __init__(self, count,prevIndex):
self.count = count;
self.prevIndex = prevIndex;
# Function to calculate the sum of
# absolute differences of indices
# of occurrences of array element
def findSum(arr,n):
# Stores the count of elements
# and their previous indices
map = {};
# Initialize 2 arrays left[]
# and right[] of size N
left = [0 for i in range(n)];
right = [0 for i in range(n)];
# Traverse the given array
for i in range(n):
# If arr[i] is present in the Map
if (arr[i] not in map):
# Update left[i] to 0
# and update the value
# of arr[i] in map
left[i] = 0;
map[arr[i]] = pair(1, i);
# Otherwise, get the value from
# the map and update left[i]
else:
tmp = map[arr[i]];
left[i] = (tmp.count) * (i - tmp.prevIndex) + left[tmp.prevIndex]
map[arr[i]] = pair( tmp.count + 1, i);
# Clear the map to calculate right[] array
map.clear();
# Traverse the array arr[] in reverse
for i in range (n - 1, -1, -1):
# If arr[i] is present in theMap
if (arr[i] not in map):
# Update right[i] to 0
# and update the value
# of arr[i] in the Map
right[i] = 0;
map[arr[i]] = pair(1, i);
# Otherwise get the value from
# the map and update right[i]
else:
tmp = map[arr[i]];
right[i] = (tmp.count) * (abs(i - tmp.prevIndex)) + right[tmp.prevIndex];
map[arr[i]] = pair(tmp.count + 1, i);
# Iterate in the range [0, N-1]
# and print the sum of left[i]
# and right[i] as the result
for i in range(n):
print(left[i] + right[i], end=" ");
# Driver Code
arr=[1, 3, 1, 1, 2];
N = len(arr);
findSum(arr, N);
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Stores the count of occurrences
// and previous index of every element
class pair {
public int count, prevIndex;
// Constructor
public pair(int count, int prevIndex)
{
this.count = count;
this.prevIndex = prevIndex;
}
}
// Function to calculate the sum of
// absolute differences of indices
// of occurrences of array element
static void findSum(int[] arr, int n)
{
// Stores the count of elements
// and their previous indices
Dictionary<int, pair> map = new Dictionary<int, pair>();
// Initialize 2 arrays []left
// and []right of size N
int[] left = new int[n];
int[] right = new int[n];
// Traverse the given array
for (int i = 0; i < n; i++) {
// If arr[i] is present in the Map
if (!map.ContainsKey(arr[i])) {
// Update left[i] to 0
// and update the value
// of arr[i] in map
left[i] = 0;
map.Add(arr[i], new pair(1, i));
}
// Otherwise, get the value from
// the map and update left[i]
else {
pair tmp = map[arr[i]];
left[i] = (tmp.count)
* (i - tmp.prevIndex)
+ left[tmp.prevIndex];
map[arr[i]] = new pair(
tmp.count + 1, i);
}
}
// Clear the map to calculate []right array
map.Clear();
// Traverse the array []arr in reverse
for (int i = n - 1; i >= 0; i--) {
// If arr[i] is present in theMap
if (!map.ContainsKey(arr[i])) {
// Update right[i] to 0
// and update the value
// of arr[i] in the Map
right[i] = 0;
map.Add(arr[i], new pair(1, i));
}
// Otherwise get the value from
// the map and update right[i]
else {
pair tmp = map[arr[i]];
right[i]
= (tmp.count)
* (Math.Abs(i - tmp.prevIndex))
+ right[tmp.prevIndex];
map[arr[i]] = new pair(
tmp.count + 1, i);
}
}
// Iterate in the range [0, N-1]
// and print the sum of left[i]
// and right[i] as the result
for (int i = 0; i < n; i++)
Console.Write(
left[i] + right[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 3, 1, 1, 2 };
int N = arr.Length;
findSum(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Stores the count of occurrences
// and previous index of every element
class pair
{
constructor(count,prevIndex)
{
this.count = count;
this.prevIndex = prevIndex;
}
}
// Function to calculate the sum of
// absolute differences of indices
// of occurrences of array element
function findSum(arr,n)
{
// Stores the count of elements
// and their previous indices
let map = new Map();
// Initialize 2 arrays left[]
// and right[] of size N
let left = new Array(n);
let right = new Array(n);
// Traverse the given array
for (let i = 0; i < n; i++) {
// If arr[i] is present in the Map
if (!map.has(arr[i])) {
// Update left[i] to 0
// and update the value
// of arr[i] in map
left[i] = 0;
map.set(arr[i], new pair(1, i));
}
// Otherwise, get the value from
// the map and update left[i]
else {
let tmp = map.get(arr[i]);
left[i] = (tmp.count)
* (i - tmp.prevIndex)
+ left[tmp.prevIndex];
map.set(
arr[i], new pair(
tmp.count + 1, i));
}
}
// Clear the map to calculate right[] array
map.clear();
// Traverse the array arr[] in reverse
for (let i = n - 1; i >= 0; i--) {
// If arr[i] is present in theMap
if (!map.has(arr[i])) {
// Update right[i] to 0
// and update the value
// of arr[i] in the Map
right[i] = 0;
map.set(arr[i], new pair(1, i));
}
// Otherwise get the value from
// the map and update right[i]
else {
let tmp = map.get(arr[i]);
right[i]
= (tmp.count)
* (Math.abs(i - tmp.prevIndex))
+ right[tmp.prevIndex];
map.set(
arr[i], new pair(
tmp.count + 1, i));
}
}
// Iterate in the range [0, N-1]
// and print the sum of left[i]
// and right[i] as the result
for (let i = 0; i < n; i++)
document.write(
left[i] + right[i] + " ");
}
// Driver Code
let arr=[1, 3, 1, 1, 2];
let N = arr.length;
findSum(arr, N);
// This code is contributed by unknown2108
</script>
Producción:
5 0 3 4 0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)