Elemento no repetitivo

Encuentre el primer elemento que no se repite en una array dada de enteros.

Ejemplos:

Input : -1 2 -1 3 2
Output : 3
Explanation : The first number that does not 
repeat is : 3

Input : 9 4 9 6 7 4
Output : 6

Una solución simple es usar dos bucles. El ciclo externo selecciona los elementos uno por uno y el ciclo interno verifica si el elemento está presente más de una vez o no.

// Simple CPP program to find first non-
// repeating element.
#include <bits/stdc++.h>
using namespace std;
 
int firstNonRepeating(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < n; j++)
            if (i != j && arr[i] == arr[j])
                break;
        if (j == n)
            return arr[i];
    }
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 9, 4, 9, 6, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << firstNonRepeating(arr, n);
    return 0;
}

// Java program to find first non-repeating
// element.
class GFG {
 
    static int firstNonRepeating(int arr[], int n)
    {
        for (int i = 0; i < n; i++) {
            int j;
            for (j = 0; j < n; j++)
                if (i != j && arr[i] == arr[j])
                    break;
            if (j == n)
                return arr[i];
        }
 
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = { 9, 4, 9, 6, 7, 4 };
        int n = arr.length;
 
        System.out.print(firstNonRepeating(arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find first
# non-repeating element.
 
def firstNonRepeating(arr, n):
 
    for i in range(n):
        j = 0
        while(j < n):
            if (i != j and arr[i] == arr[j]):
                break
            j += 1
        if (j == n):
            return arr[i]
     
    return -1
     
# Driver code
arr = [ 9, 4, 9, 6, 7, 4 ]
n = len(arr)
print(firstNonRepeating(arr, n))
 
# This code is contributed by Anant Agarwal.

// C# program to find first non-
// repeating element.
using System;
 
class GFG {
    static int firstNonRepeating(int[] arr, int n)
    {
        for (int i = 0; i < n; i++) {
            int j;
            for (j = 0; j < n; j++)
                if (i != j && arr[i] == arr[j])
                    break;
            if (j == n)
                return arr[i];
        }
        return -1;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 9, 4, 9, 6, 7, 4 };
        int n = arr.Length;
        Console.Write(firstNonRepeating(arr, n));
    }
}
// This code is contributed by Anant Agarwal.

<?php
// Simple PHP program to find first non-
// repeating element.
 
function firstNonRepeating($arr, $n)
{
    for ($i = 0; $i < $n; $i++)
    {
        $j;
        for ($j = 0; $j< $n; $j++)
            if ($i != $j && $arr[$i] == $arr[$j])
                break;
        if ($j == $n)
            return $arr[$i];
    }
    return -1;
}
 
    // Driver code
    $arr = array(9, 4, 9, 6, 7, 4);
    $n = sizeof($arr) ;
    echo firstNonRepeating($arr, $n);
     
// This code is contributed by ajit
?>

  <script>
      // JavaScript code for the above approach
      function firstNonRepeating(arr, n) {
          for (let i = 0; i < n; i++) {
              let j;
              for (j = 0; j < n; j++)
                  if (i != j && arr[i] == arr[j])
                      break;
              if (j == n)
                  return arr[i];
          }
          return -1;
      }
 
      // Driver code
 
      let arr = [9, 4, 9, 6, 7, 4];
      let n = arr.length;
      document.write(firstNonRepeating(arr, n));
 
 
 
// This code is contributed by Potta Lokesh
  </script>

6

Complejidad temporal: O(n*n)
Espacio auxiliar: O(1)

Una solución eficiente es usar hashing.
1) Atraviese la array e inserte elementos y sus recuentos en la tabla hash.
2) Atraviese la array nuevamente e imprima el primer elemento con un recuento igual a 1.

// Efficient CPP program to find first non-
// repeating element.
#include <bits/stdc++.h>
using namespace std;
 
int firstNonRepeating(int arr[], int n)
{
    // Insert all array elements in hash
    // table
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
 
    // Traverse array again and return
    // first element with count 1.
    for (int i = 0; i < n; i++)
        if (mp[arr[i]] == 1)
            return arr[i];
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 9, 4, 9, 6, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << firstNonRepeating(arr, n);
    return 0;
}

// Efficient Java program to find first non-
// repeating element.
import java.util.*;
 
class GFG {
 
    static int firstNonRepeating(int arr[], int n)
    {
        // Insert all array elements in hash
        // table
 
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (m.containsKey(arr[i])) {
                m.put(arr[i], m.get(arr[i]) + 1);
            }
            else {
                m.put(arr[i], 1);
            }
        }
        // Traverse array again and return
        // first element with count 1.
        for (int i = 0; i < n; i++)
            if (m.get(arr[i]) == 1)
                return arr[i];
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 9, 4, 9, 6, 7, 4 };
        int n = arr.length;
        System.out.println(firstNonRepeating(arr, n));
    }
}
 
// This code contributed by Rajput-Ji

# Efficient Python3 program to find first
# non-repeating element.
from collections import defaultdict
 
def firstNonRepeating(arr, n):
    mp = defaultdict(lambda:0)
 
    # Insert all array elements in hash table
    for i in range(n):
        mp[arr[i]] += 1
 
    # Traverse array again and return
    # first element with count 1.
    for i in range(n):
        if mp[arr[i]] == 1:
            return arr[i]
    return -1
 
# Driver Code
arr = [9, 4, 9, 6, 7, 4]
n = len(arr)
print(firstNonRepeating(arr, n))
 
# This code is contributed by Shrikant13

// Efficient C# program to find first non-
// repeating element.
using System;
using System.Collections.Generic;
 
class GFG {
 
    static int firstNonRepeating(int[] arr, int n)
    {
        // Insert all array elements in hash
        // table
 
        Dictionary<int, int> m = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            if (m.ContainsKey(arr[i])) {
                var val = m[arr[i]];
                m.Remove(arr[i]);
                m.Add(arr[i], val + 1);
            }
            else {
                m.Add(arr[i], 1);
            }
        }
 
        // Traverse array again and return
        // first element with count 1.
        for (int i = 0; i < n; i++)
            if (m[arr[i]] == 1)
                return arr[i];
        return -1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 9, 4, 9, 6, 7, 4 };
        int n = arr.Length;
        Console.WriteLine(firstNonRepeating(arr, n));
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
// Efficient javascript program to find first non-
// repeating element.
 
function firstNonRepeating(arr , n)
{
    // Insert all array elements in hash
    // table
 
    const m = new Map();
    for (var i = 0; i < n; i++) {
        if (m.has(arr[i])) {
            m.set(arr[i], m.get(arr[i]) + 1);
        }
        else {
            m.set(arr[i], 1);
        }
    }
    // Traverse array again and return
    // first element with count 1.
    for (var i = 0; i < n; i++)
        if (m.get(arr[i]) == 1)
            return arr[i];
    return -1;
}
 
// Driver code
var arr = [ 9, 4, 9, 6, 7, 4 ];
var n = arr.length;
document.write(firstNonRepeating(arr, n));
 
// This code contributed by shikhasingrajput
</script>

6

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Optimización adicional: si la array tiene muchos duplicados, también podemos almacenar el índice en la tabla hash, usando una tabla hash donde el valor es un par . Ahora solo necesitamos recorrer las claves en la tabla hash (no en la array completa) para encontrar la primera que no se repite.

Imprimiendo todos los elementos que no se repiten:

// Efficient CPP program to print all non-
// repeating elements.
#include <bits/stdc++.h>
using namespace std;
 
void firstNonRepeating(int arr[], int n)
{
    // Insert all array elements in hash
    // table
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
 
    // Traverse through map only and
    for (auto x : mp)
        if (x.second == 1)
            cout << x.first << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 9, 4, 9, 6, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    firstNonRepeating(arr, n);
    return 0;
}

// Efficient Java program to print all non-
// repeating elements.
import java.util.*;
 
class GFG {
 
    static void firstNonRepeating(int arr[], int n)
    {
        // Insert all array elements in hash
        // table
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (m.containsKey(arr[i])) {
                m.put(arr[i], m.get(arr[i]) + 1);
            }
            else {
                m.put(arr[i], 1);
            }
        }
 
        // Traverse through map only and
        // using for-each loop for iteration over Map.entrySet()
        for (Map.Entry<Integer, Integer> x : m.entrySet())
            if (x.getValue() == 1)
                System.out.print(x.getKey() + " ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 9, 4, 9, 6, 7, 4 };
        int n = arr.length;
        firstNonRepeating(arr, n);
    }
}
 
// This code has been contributed by 29AjayKumar

# Efficient Python program to print all non-
# repeating elements.
 
def firstNonRepeating(arr, n):
     
    # Insert all array elements in hash
    # table
    mp={}
    for i in range(n):
        if arr[i] not in mp:
            mp[arr[i]]=0
        mp[arr[i]]+=1
         
    # Traverse through map only and
    for x in mp:
        if (mp[x]== 1):
            print(x,end=" ")
             
# Driver code
arr = [ 9, 4, 9, 6, 7, 4 ]
n = len(arr)
firstNonRepeating(arr, n)
  
# This code is contributed by shivanisinghss2110

// Efficient C# program to print all non-
// repeating elements.
using System;
using System.Collections.Generic;
 
class GFG {
 
    static void firstNonRepeating(int[] arr, int n)
    {
        // Insert all array elements in hash
        // table
        Dictionary<int, int> m = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            if (m.ContainsKey(arr[i])) {
                var val = m[arr[i]];
                m.Remove(arr[i]);
                m.Add(arr[i], val + 1);
            }
            else {
                m.Add(arr[i], 1);
            }
        }
 
        // Traverse through map only and
        // using for-each loop for iteration over Map.entrySet()
        foreach(KeyValuePair<int, int> x in m)
        {
            if (x.Value == 1) {
                Console.Write(x.Key + " ");
            }
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 9, 4, 9, 6, 7, 4 };
        int n = arr.Length;
        firstNonRepeating(arr, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
// Efficient Javascript program to print all non-
// repeating elements.
 
function firstNonRepeating(arr, n)
{
    // Insert all array elements in hash
    // table
    const mp = new Map();
    for (var i = 0; i< n; i++)
    {
        if(mp.has(arr[i]))
        mp.set(arr[i], mp.get(arr[i]) + 1);
        else
        mp.set(arr[i],1);
         
    }
     
    // Traverse through map only and
    for (var x of mp.keys())
    {    
         
        if (mp.get(x) == 1)
          document.write(x+" ");  
    }  
}
 
// Driver code
 
    var arr = [ 9, 4, 9, 6, 7, 4 ];
    var n = arr.length;
    firstNonRepeating(arr, n);
  
// This code contributed by Palak Gupta
</script>

7 6

Complejidad temporal: O(n)
Espacio auxiliar: O(n)