Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar el número total de pares no ordenados (i, j) en el arreglo tal que arr[i] sea igual a arr[j] e i < j para todos los subarreglos de la array dada .
Ejemplos:
Entrada: arr[] = {1, 2, 1, 1}
Salida: 6
Explicación: Todos los subarreglos de la array dada de tamaño mayor que 1 son:
- {1, 2}: No hay tales pares que satisfagan los criterios dados. Por lo tanto, el conteo de pares para el subarreglo actual es 0.
- {2, 1}: No hay tales pares que satisfagan los criterios dados. Por lo tanto, el conteo de pares para el subarreglo actual es 0.
- {1, 1}: Los pares que cumplen los criterios dados son (0, 1). Por lo tanto, el conteo de pares para el subarreglo actual es 1.
- {1, 2, 1}: Los pares que cumplen los criterios dados son (0, 2). Por lo tanto, el conteo de pares para el subarreglo actual es 1.
- {2, 1, 1}: Los pares que cumplen los criterios dados son (1, 1). Por lo tanto, el conteo de pares para el subarreglo actual es 1.
- {1, 2, 1, 1}: los pares que cumplen los criterios dados son (0, 2), (0, 3) y (2, 3). Por lo tanto, el conteo de pares para el subarreglo actual es 3.
Por lo tanto, el recuento total de todos los subarreglos = 1 + 1 + 1 + 3 = 6.
Entrada: arr[] = {1, 2, 1, 3}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles de un tamaño mayor que 1 y encontrar la suma del recuento de pares que satisfacen los criterios dados para todos los subarreglos posibles del arreglo dado.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando todas las posiciones correspondientes a cada elemento distinto en un mapa y luego, para cada elemento, recorrer las posiciones correspondientes a ese elemento y calcular el número de subarreglos en los que se produce cada par. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa M con claves como un par y valores como un vector .
- Inicialice otra variable, digamos ans como 0 que almacena el recuento total de pares que satisfacen los criterios dados.
- Recorra la array dada arr[] usando la variable i y agregue el valor de i a la clave M[arr[i]] .
- Recorra el mapa M y realice los siguientes pasos:
- Inicialice un vector, diga V como el valor correspondiente a la clave actual.
- Inicializar una variable, digamos sum as 0 .
- Atraviese el vector V dado para cada elemento V[j] agregue el valor de (sum*(N – V[j])) a la variable ans y agregue el valor (V[j] + 1) a la variable sum .
- Después de completar los pasos anteriores, imprima el valor de ans 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 count all pairs (i, j)
// such that arr[i] equals arr[j] in
// all possible subarrays of the array
void countPairs(vector<int> arr)
{
// Stores the size of the array
int N = arr.size();
int ans = 0;
// Stores the positions of all
// the distinct elements
map<int, vector<int> > M;
// Append index corresponding
// to arr[i] in the map
for (int i = 0;
i < arr.size(); i++) {
M[arr[i]].push_back(i);
}
// Traverse the map M
for (auto it : M) {
vector<int> v = it.second;
int sum = 0;
// Traverse the array
for (int j = 0;
j < v.size(); j++) {
// Update the value of
// ans
ans += sum * (N - v[j]);
// Update the value of
// the sum
sum += v[j] + 1;
}
}
// Print the value of ans
cout << ans;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 1, 1 };
countPairs(arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
import java.util.List;
import com.google.common.collect.*;
class GFG {
// Function to count all pairs (i, j)
// such that arr[i] equals arr[j] in
// all possible subarrays of the array
static void countPairs(int[] arr)
{
// Stores the size of the array
int N = arr.length;
int ans = 0;
// Stores the positions of all
// the distinct elements
ListMultimap<Integer, Integer> M = ArrayListMultimap.create();
// Append index corresponding
// to arr[i] in the map
for (int i = 0;
i < arr.length; i++) {
M.put(arr[i], i);
}
// Traverse the map M
for (var it: M.keySet()) {
List<Integer> v = M.get(it);
int sum = 0;
// Traverse the array
for (int j : v) {
// Update the value of
// ans
ans += sum * (N - j);
// Update the value of
// the sum
sum += j + 1;
}
}
// Print the value of ans
System.out.println(ans);
}
// Driver Code
public static void main (String[] args) {
int[] arr = { 1, 2, 1, 1 };
countPairs(arr);
}
}
// This Code is contributed by ShubhamSingh10
Python3
# Python3 program for the above approach
# Function to count all pairs (i, j)
# such that arr[i] equals arr[j] in
# all possible subarrays of the array
def countPairs(arr):
# Stores the size of the array
N = len(arr)
ans = 0
# Stores the positions of all
# the distinct elements
M = {}
# Append index corresponding
# to arr[i] in the map
for i in range(len(arr)):
if arr[i] in M:
M[arr[i]].append(i)
else:
M[arr[i]] = [i]
# Traverse the map M
for key, value in M.items():
v = value
sum1 = 0
# Traverse the array
for j in range(len(v)):
# Update the value of
# ans
ans += (sum1 * (N - v[j]))
# Update the value of
# the sum
sum1 += v[j] + 1
# Print the value of ans
print(ans)
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 1, 1 ]
countPairs(arr)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count all pairs (i, j)
// such that arr[i] equals arr[j] in
// all possible subarrays of the array
static void countPairs(int[] arr)
{
// Stores the size of the array
int N = arr.Length;
int ans = 0;
// Stores the positions of all
// the distinct elements
Dictionary<int, List<int>> M = new Dictionary<int, List<int>>();
// Append index corresponding
// to arr[i] in the map
for (int i = 0 ; i < arr.Length ; i++) {
if(!M.ContainsKey(arr[i])){
M.Add(arr[i], new List<int>());
}
M[arr[i]].Add(i);
}
// Traverse the map M
foreach (KeyValuePair<int, List<int>> it in M) {
List<int> v = it.Value;
int sum = 0;
// Traverse the array
foreach (int j in v) {
// Update the value of
// ans
ans += sum * (N - j);
// Update the value of
// the sum
sum += j + 1;
}
}
// Print the value of ans
Console.Write(ans);
}
// Driver Code
public static void Main(string[] args){
int[] arr = new int[]{ 1, 2, 1, 1 };
countPairs(arr);
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript program for the above approach
// Function to count all pairs (i, j)
// such that arr[i] equals arr[j] in
// all possible subarrays of the array
function countPairs(arr) {
// Stores the size of the array
let N = arr.length;
let ans = 0;
// Stores the positions of all
// the distinct elements
let M = new Map();
// Append index corresponding
// to arr[i] in the map
for (let i = 0; i < arr.length; i++) {
if (M.has(arr[i])) {
M.get(arr[i]).push(i);
} else {
M.set(arr[i], [i])
}
}
// Traverse the map M
for (let it of M) {
let v = it[1];
let sum = 0;
// Traverse the array
for (let j = 0; j < v.length; j++) {
// Update the value of
// ans
ans += sum * (N - v[j]);
// Update the value of
// the sum
sum += v[j] + 1;
}
}
// Print the value of ans
document.write(ans);
}
// Driver Code
let arr = [1, 2, 1, 1];
countPairs(arr);
</script>
Producción:
6
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nitishvaishnav2017 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA