Encuentre el único elemento que no se repite en una array dada

Dado un arreglo A[] que consta de N ( 1 ≤ N ≤ 10 ⁵ ) enteros positivos, la tarea es encontrar el único elemento del arreglo con una sola ocurrencia. 

Nota: Se garantiza que solo existe uno de esos elementos en la array.

Ejemplos:

Entrada: A[] = {1, 1, 2, 3, 3}
Salida: 2
Explicación: 
Los distintos elementos de la array son {1, 2, 3}. 
La frecuencia de estos elementos es {2, 1, 2} respectivamente.

Entrada : A[] = {1, 1, 1, 2, 2, 3, 5, 3, 4, 4}
Salida : 5

Enfoque: siga los pasos a continuación para resolver el problema

1. Atraviesa la array
2. Utilice un mapa desordenado para almacenar la frecuencia de los elementos de la array .
3. Recorra el Mapa y encuentre el elemento con frecuencia 1 e imprima ese elemento.

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

// C++ implementation of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function call to find
// element in A[] with frequency = 1
void CalcUnique(int A[], int N)
{
    // Stores frequency of
    // array elements
    unordered_map<int, int> freq;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Update frequency of A[i]
        freq[A[i]]++;
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++) {
 
        // If non-repeating element
        // is found
        if (freq[A[i]] == 1) {
 
            cout << A[i];
            return;
        }
    }
}
 
// Driver Code
int main()
{
    int A[] = { 1, 1, 2, 3, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    CalcUnique(A, N);
 
    return 0;
}

// Java implementation of the
// above approach
import java.util.*;
class GFG
{
 
  // Function call to find
  // element in A[] with frequency = 1
  static void CalcUnique(int A[], int N)
  {
    // Stores frequency of
    // array elements
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Update frequency of A[i]
      if(freq.containsKey(A[i]))
      {
        freq.put(A[i], freq.get(A[i]) + 1);
      }
      else
      {
        freq.put(A[i], 1);
      }
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++)
    {
 
      // If non-repeating element
      // is found
      if (freq.containsKey(A[i])&&freq.get(A[i]) == 1)
      {
        System.out.print(A[i]);
        return;
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int A[] = { 1, 1, 2, 3, 3 };
    int N = A.length;
    CalcUnique(A, N);
  }
}
 
// This code is contributed by 29AjayKumar

# Python 3 implementation of the
# above approach
from collections import defaultdict
 
# Function call to find
# element in A[] with frequency = 1
def CalcUnique(A, N):
 
    # Stores frequency of
    # array elements
    freq = defaultdict(int)
 
    # Traverse the array
    for i in range(N):
 
        # Update frequency of A[i]
        freq[A[i]] += 1
 
    # Traverse the Map
    for i in range(N):
 
        # If non-repeating element
        # is found
        if (freq[A[i]] == 1):
            print(A[i])
            return
 
# Driver Code
if __name__ == "__main__":
    A = [1, 1, 2, 3, 3]
    N = len(A)
    CalcUnique(A, N)
 
    # This code is contributed by chitranayal.

// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function call to find
  // element in []A with frequency = 1
  static void CalcUnique(int []A, int N)
  {
     
    // Stores frequency of
    // array elements
    Dictionary<int,int> freq = new Dictionary<int,int>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Update frequency of A[i]
      if(freq.ContainsKey(A[i]))
      {
        freq[A[i]] = freq[A[i]] + 1;
      }
      else
      {
        freq.Add(A[i], 1);
      }
    }
 
    // Traverse the Map
    for (int i = 0; i < N; i++)
    {
 
      // If non-repeating element
      // is found
      if (freq.ContainsKey(A[i]) && freq[A[i]] == 1)
      {
        Console.Write(A[i]);
        return;
      }
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []A = { 1, 1, 2, 3, 3 };
    int N = A.Length;
    CalcUnique(A, N);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the
// above approach
 
// Function call to find
// element in A[] with frequency = 1
function CalcUnique(A, N)
{
    // Stores frequency of
    // array elements
    var freq = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Update frequency of A[i]
        if(freq.has(A[i]))
        {
            freq.set(A[i], freq.get(A[i])+1);
        }
        else
        {
            freq.set(A[i],1);
        }
    }
 
    // Traverse the Map
    for (var i = 0; i < N; i++) {
 
        // If non-repeating element
        // is found
        if (freq.get(A[i]) == 1) {
 
            document.write( A[i]);
            return;
        }
    }
}
 
// Driver Code
var A = [1, 1, 2, 3, 3 ];
var N = A.length;
CalcUnique(A, N);
 
</script>

2

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)

Otro enfoque: uso de funciones integradas de Python:

• Calcule las frecuencias usando la función Counter() .
• Recorra la array y encuentre el elemento con frecuencia 1 e imprímalo.

A continuación se muestra la implementación:

# Python 3 implementation of the
# above approach
from collections import Counter
 
# Function call to find
# element in A[] with frequency = 1
def CalcUnique(A, N):
 
    # Calculate frequency of
    # all array elements
    freq = Counter(A)
     
    # Traverse the Array
    for i in A:
 
        # If non-repeating element
        # is found
        if (freq[i] == 1):
            print(i)
            return
 
 
# Driver Code
if __name__ == "__main__":
    A = [1, 1, 2, 3, 3]
    N = len(A)
    CalcUnique(A, N)
 
# This code is contributed by vikkycirus

Producción:

2

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)