Recuento de pares únicos (arr[i], arr[j]) tales que i < j

Dado un arreglo arr[] , la tarea es imprimir el conteo de pares únicos (arr[i], arr[j]) tales que i < j .

Ejemplos: 

Entrada: arr[] = {1, 2, 1, 4, 5, 2} 
Salida: 11 
Los pares posibles son (1, 2), (1, 1), (1, 4), (1, 5), (2, 1), (2, 4), (2, 5), (2, 2), (4, 5), (4, 2), (5, 2)

Entrada: arr[] = {1, 2, 3, 4} 
Salida:
Los pares posibles son (1, 2), (1, 3), (1, 4), (2, 3), (2, 4) ), (3, 4) 

Enfoque ingenuo: la forma más fácil es iterar a través de cada par posible y, si cumple la condición, agregarlo a un conjunto. Luego, podemos devolver el tamaño del conjunto como nuestra respuesta.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <iostream>
#include <set>
using namespace std;
  
// Function to return the count 
// of unique pairs in the array 
int getPairs(int arr[], int n)
{
    // Set to store unique pairs 
    set<pair<int, int>> h;
    for(int i = 0; i < (n - 1); i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // Create pair of (arr[i], arr[j]) 
            // and add it to the hashset 
            h.insert(make_pair(arr[i], arr[j])); 
        }
    }
     
    // Return the size of the HashSet 
    return h.size();
}
     
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
    int  n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", getPairs(arr, n)) ;
    return 0;
}
  
// This code is contributed by SHUBHAMSINGH10

Java

// Java implementation of the approach
import java.util.HashSet;
import javafx.util.Pair;
 
class GFG {
 
    // Function to return the count
    // of unique pairs in the array
    static int getPairs(int arr[], int n)
    {
 
        // HashSet to store unique pairs
        HashSet<Pair> h = new HashSet<Pair>();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
 
                // Create pair of (a[i], a[j])
                // and add it to the hashset
                Pair<Integer, Integer> p
                    = new Pair<>(arr[i], arr[j]);
                h.add(p);
            }
        }
 
        // Return the size of the HashSet
        return h.size();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
        int n = arr.length;
        System.out.println(getPairs(arr, n));
    }
}

Python3

# Python3 implementation of the approach
  
# Function to return the count
# of unique pairs in the array
def getPairs(arr, n) :
      
    # Set to store unique pairs
    h = set()
    for i in range(n - 1) :
        for j in range(i + 1, n) :
             
            # Create pair of (a[i], a[j])
            # and add it to the hashset
            h.add((arr[i], arr[j]));
              
    # Return the size of the HashSet
    return len(h);
  
# Driver code
if __name__ == "__main__" :
       
    arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ]
    n = len(arr)
      
    print(getPairs(arr, n))
      
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the count
// of unique pairs in the array
static int getPairs(int []arr, int n)
{
     
    // HashSet to store unique pairs
    HashSet<Tuple<int,
                  int>> h = new HashSet<Tuple<int,
                                              int>>();
                                               
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
             
            // Create pair of (a[i], a[j])
            // and add it to the hashset
            Tuple<int,
                  int> p = new Tuple<int,
                                     int>(arr[i],
                                          arr[j]);
            h.Add(p);
        }
    }
 
    // Return the size of the HashSet
    return h.Count;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 2, 4, 2, 5, 3, 5 };
    int n = arr.Length;
     
    Console.WriteLine(getPairs(arr, n));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript implementation of the approach
  
// Function to return the count 
// of unique pairs in the array 
function getPairs(arr, n)
{
    // Set to store unique pairs
    var h = new Set();
    for(var i = 0; i < (n - 1); i++)
    {
        for (var j = i + 1; j < n; j++)
        {
            // Create pair of (arr[i], arr[j]) 
            // and add it to the hashset 
            h.add([arr[i], arr[j]]);  
        }
    }
    // Return the size of the HashSet 
    return h.size/2;
}
     
// Driver code
var arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ];
var  n = arr.length;
document.write(getPairs(arr, n));
  
// This code is contributed by SHUBHAMSINGH10
 
</script>
Producción: 

14

 

Complejidad temporal: O(n 2

Nota: utilice un IDE sin conexión para compilar el código anterior. Es posible que los compiladores en línea no admitan JavaFX.

Enfoque eficiente: cada elemento arr[i] puede formar un par con el elemento arr[j] si i < j . Pero (arr[i], arr[j]) debe ser único, por lo tanto, para cada único arr[i] , los posibles pares serán iguales al número de números distintos en el subarreglo arr[i + 1], arr[i + 2], …, arr[n – 1] . Entonces, para cada arr[i] , encontraremos los elementos únicos de derecha a izquierda. Para esta tarea, es fácil realizar un seguimiento de los elementos visitados mediante una tabla Hash. De esta forma, tendremos un único arr[i] para cada único arr[j] . Ahora, sumaremos estos valores para cada arr[i] únicoque es el número deseado de pares.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of unique pairs in the array
int getPairs(int a[], int n)
{
    set<int> visited1;
 
    // un[i] stores number of unique elements
    // from un[i + 1] to un[n - 1]
    int un[n] ;
 
    // Last element will have no unique elements
    // after it
    un[n - 1] = 0;
 
    // To count unique elements after every a[i]
    int count = 0;
     // auto pos = s.find(3);
 
     // prints the set elements
     // cout << "The set elements after 3 are: ";
     // for (auto it = pos; it != s.end(); it++)
    // cout << *it << " "
    for (int i = n - 1; i > 0; i--)
    {
 
        // If current element has already been used
        // i.e. not unique
        auto pos = visited1.find(a[i]);
        if (pos != visited1.end())
            un[i - 1] = count;
        else
            un[i - 1] = ++count;
 
        // Set to true if a[i] is visited
        visited1.insert(a[i]);
    }
 
    set<int>visited2;
 
    // To know which a[i] is already visited
    int answer = 0;
    for (int i = 0; i < n - 1; i++)
    {
 
        // If visited, then the pair would
        // not be unique
        auto pos = visited2.find(a[i]);
        if (pos != visited2.end())
            continue;
 
        // Calculating total unique pairs
        answer += un[i];
 
        // Set to true if a[i] is visited
        visited2.insert(a[i]);
    }
    return answer;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
    int n = sizeof(a)/sizeof(a[0]);
 
    // Print the count of unique pairs
    cout<<(getPairs(a, n));
}
 
// This code is contributed by Rajput-Ji

Java

// Java implementation of the approach
import java.util.HashSet;
 
public class GFG {
 
    // Function to return the count
    // of unique pairs in the array
    static int getPairs(int a[], int n)
    {
        HashSet<Integer> visited1 = new HashSet<Integer>();
 
        // un[i] stores number of unique elements
        // from un[i + 1] to un[n - 1]
        int un[] = new int[n];
 
        // Last element will have no unique elements
        // after it
        un[n - 1] = 0;
 
        // To count unique elements after every a[i]
        int count = 0;
        for (int i = n - 1; i > 0; i--) {
 
            // If current element has already been used
            // i.e. not unique
            if (visited1.contains(a[i]))
                un[i - 1] = count;
            else
                un[i - 1] = ++count;
 
            // Set to true if a[i] is visited
            visited1.add(a[i]);
        }
 
        HashSet<Integer> visited2 = new HashSet<Integer>();
 
        // To know which a[i] is already visited
        int answer = 0;
        for (int i = 0; i < n - 1; i++) {
 
            // If visited, then the pair would
            // not be unique
            if (visited2.contains(a[i]))
                continue;
 
            // Calculating total unique pairs
            answer += un[i];
 
            // Set to true if a[i] is visited
            visited2.add(a[i]);
        }
        return answer;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
        int n = a.length;
 
        // Print the count of unique pairs
        System.out.println(getPairs(a, n));
    }
}

Python3

# Python3 implementation of the approach
 
# Function to return the count
# of unique pairs in the array
def getPairs(a, n):
     
    visited1 = set()
     
    # un[i] stores number of unique elements
    # from un[i + 1] to un[n - 1]
    un = [0] * n
     
    # Last element will have no unique elements
    # after it
    un[n - 1] = 0
     
    # To count unique elements after every a[i]
    count = 0
    for i in range(n - 1, -1, -1):
         
        # If current element has already been used
        # i.e. not unique
        if (a[i] in visited1):
            un[i - 1] = count
        else:
            count += 1
            un[i - 1] = count
         
        # Set to true if a[i] is visited
        visited1.add(a[i])
     
    visited2 = set()
     
    # To know which a[i] is already visited
    answer = 0
    for i in range(n - 1):
         
        # If visited, then the pair would
        # not be unique
        if (a[i] in visited2):
            continue
             
        # Calculating total unique pairs
        answer += un[i]
         
        # Set to true if a[i] is visited
        visited2.add(a[i])
     
    return answer
 
# Driver code
 
a = [1, 2, 2, 4, 2, 5, 3, 5]
n = len(a)
 
# Print the count of unique pairs
print(getPairs(a, n))
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to return the count
    // of unique pairs in the array
    static int getPairs(int []a, int n)
    {
        HashSet<int> visited1 = new HashSet<int>();
 
        // un[i] stores number of unique elements
        // from un[i + 1] to un[n - 1]
        int []un = new int[n];
 
        // Last element will have no unique elements
        // after it
        un[n - 1] = 0;
 
        // To count unique elements after every a[i]
        int count = 0;
        for (int i = n - 1; i > 0; i--)
        {
 
            // If current element has already been used
            // i.e. not unique
            if (visited1.Contains(a[i]))
                un[i - 1] = count;
            else
                un[i - 1] = ++count;
 
            // Set to true if a[i] is visited
            visited1.Add(a[i]);
        }
 
        HashSet<int> visited2 = new HashSet<int>();
 
        // To know which a[i] is already visited
        int answer = 0;
        for (int i = 0; i < n - 1; i++)
        {
 
            // If visited, then the pair would
            // not be unique
            if (visited2.Contains(a[i]))
                continue;
 
            // Calculating total unique pairs
            answer += un[i];
 
            // Set to true if a[i] is visited
            visited2.Add(a[i]);
        }
        return answer;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []a = { 1, 2, 2, 4, 2, 5, 3, 5 };
        int n = a.Length;
 
        // Print the count of unique pairs
        Console.WriteLine(getPairs(a, n));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript Program to implement
// the above approach
 
   // Function to return the count
    // of unique pairs in the array
    function getPairs(a, n)
    {
        let visited1 = new Set();
 
        // un[i] stores number of unique elements
        // from un[i + 1] to un[n - 1]
        let un = Array.from({length: n}, (_, i) => 0);
 
        // Last element will have no unique elements
        // after it
        un[n - 1] = 0;
 
        // To count unique elements after every a[i]
        let count = 0;
        for (let i = n - 1; i > 0; i--) {
 
            // If current element has already been used
            // i.e. not unique
            if (visited1.has(a[i]))
                un[i - 1] = count;
            else
                un[i - 1] = ++count;
 
            // Set to true if a[i] is visited
            visited1.add(a[i]);
        }
 
        let visited2 = new Set();
 
        // To know which a[i] is already visited
        let answer = 0;
        for (let i = 0; i < n - 1; i++) {
 
            // If visited, then the pair would
            // not be unique
            if (visited2.has(a[i]))
                continue;
 
            // Calculating total unique pairs
            answer += un[i];
 
            // Set to true if a[i] is visited
            visited2.add(a[i]);
        }
        return answer;
    }
 
// Driver Code
 
    let a = [ 1, 2, 2, 4, 2, 5, 3, 5 ];
        let n = a.length;
 
        // Print the count of unique pairs
        document.write(getPairs(a, n));
 
</script>
Producción: 

14

 

Complejidad de tiempo: O (nlogn)
 

Publicación traducida automáticamente

Artículo escrito por Shivam_72 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 *