Suma de diferencias absolutas de índices de ocurrencias de cada elemento de la array | conjunto 2

 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)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *