Elemento no repetitivo más grande

Dada una array arr[] de tamaño N , la tarea es encontrar el elemento no repetido más grande presente en la array dada. Si no existe tal elemento, imprima -1 .

Ejemplos:

Entrada: arr[] = { 3, 1, 8, 8, 4 } 
Salida: 4 
Explicación: 
Los elementos no repetidos de la array dada son { 1, 3, 4 } 
Por lo tanto, el elemento no repetido más grande de la array dada es 4

Entrada: arr[] = { 3, 1, 8, 8, 3 } 
Salida: 1 
Explicación: 
Los elementos no repetidos de la array dada son { 1 } 
Por lo tanto, el elemento no repetido más grande de la array dada es 1.

Enfoque: El problema se puede resolver usando Hashing . Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa , digamos mp , para almacenar la frecuencia de cada elemento distinto de la array .
• Atraviese la array y almacene las frecuencias de cada elemento de la array .
• Inicialice una variable, digamos LNRElem para almacenar el elemento no repetido más grande presente en la array.
• Recorra la array y para cada i ^-ésimo elemento, verifique si la frecuencia de arr[i] en la array es igual a 1 o no. Si se determina que es cierto, actualice LNRElem = max(LNRElem, arr[i]) .
• Finalmente, imprima el valor de LNRElem .

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest unique
// element of the array
void LarUnEl(int arr[], int N)
{
    // Store frequency of each
    // distinct array element
    unordered_map<int, int> mp;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Update frequency of arr[i]
        mp[arr[i]]++;
    }
 
    // Stores largest non-repeating
    // element present in the array
    int LNRElem = INT_MIN;
 
    // Stores index of the largest
    // unique element of the array
    int ind = -1;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If frequency of arr[i] is equal
        // to 1 and arr[i] exceeds LNRElem
        if (mp[arr[i]] == 1
            && arr[i] > LNRElem) {
 
            // Update ind
            ind = i;
 
            // Update LNRElem
            LNRElem = arr[i];
        }
    }
 
    // If no array element is found
    // with frequency equal to 1
    if (ind == -1) {
        cout << ind;
        return;
    }
 
    // Print the largest
    // non-repeating element
    cout << arr[ind];
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 1, 8, 8, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    LarUnEl(arr, N);
}

// Java program to implement
// the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the largest unique
    // element of the array
    static void LarUnEl(int arr[], int N)
    {
 
        // Store frequency of each distinct
        // element of the array
        HashMap<Integer, Integer> map
            = new HashMap<Integer, Integer>();
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // Update frequency of arr[i]
            map.put(arr[i],
                    map.getOrDefault(arr[i], 0) + 1);
        }
 
        // Stores largest non-repeating
        // element present in the array
        int LNRElem = Integer.MIN_VALUE;
 
        // Stores index of the largest
        // non-repeating array element
        int ind = -1;
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If frequency of arr[i] is equal
            // to 1 and arr[i] exceeds LNRElem
            if (map.get(arr[i]) == 1
                && arr[i] > LNRElem) {
 
                // Update ind
                ind = i;
 
                // Update LNRElem
                LNRElem = arr[i];
            }
        }
 
        // If no array element is found
        // with frequency equal to 1
        if (ind == -1) {
            System.out.println(ind);
            return;
        }
 
        // Print largest non-repeating element
        System.out.println(arr[ind]);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 1, 8, 8, 4 };
        int N = arr.length;
        LarUnEl(arr, N);
    }
}

# Python program to implement
# the above approach
import sys
 
# Function to find the largest unique
# element of the array
def LarUnEl(arr, N):
   
    # Store frequency of each distinct
    # element of the array
    map = dict.fromkeys(arr, 0);
 
    # Traverse the array
    for i in range(N):
       
        # Update frequency of arr[i]
        map[arr[i]] += 1;
         
    # Stores largest non-repeating
    # element present in the array
    LNRElem = -sys.maxsize;
 
    # Stores index of the largest
    # non-repeating array element
    ind = -1;
 
    # Traverse the array
    for i in range(N):
 
        # If frequency of arr[i] is equal
        # to 1 and arr[i] exceeds LNRElem
        if (map.get(arr[i]) == 1 and arr[i] > LNRElem):
             
            # Update ind
            ind = i;
 
            # Update LNRElem
            LNRElem = arr[i];
 
    # If no array element is found
    # with frequency equal to 1
    if (ind == -1):
        print(ind);
        return;
 
    # Print largest non-repeating element
    print(arr[ind]);
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 1, 8, 8, 4];
    N = len(arr);
    LarUnEl(arr, N);
 
    # This code is contributed by shikhasingrajput

// C# program to implement
// the above approach 
using System;
using System.Collections.Generic;
 
class GFG {
      
    // Function to find the largest unique
    // element of the array
    static void LarUnEl(int[] arr, int N)
    {
  
        // Store frequency of each distinct
        // element of the array
        Dictionary<int,
               int> map = new Dictionary<int,
                                        int>();
  
        // Traverse the array
        for (int i = 0; i < N; i++) {
  
            // Update frequency of arr[i]
            if (map.ContainsKey(arr[i]) == true)
                map[arr[i]] += 1;
            else
                map[arr[i]] = 1;
            }
  
        // Stores largest non-repeating
        // element present in the array
        int LNRElem = Int32.MinValue;
  
        // Stores index of the largest
        // non-repeating array element
        int ind = -1;
  
        // Traverse the array
        for (int i = 0; i < N; i++) {
  
            // If frequency of arr[i] is equal
            // to 1 and arr[i] exceeds LNRElem
            if (map[arr[i]] == 1
                && arr[i] > LNRElem) {
  
                // Update ind
                ind = i;
  
                // Update LNRElem
                LNRElem = arr[i];
            }
        }
  
        // If no array element is found
        // with frequency equal to 1
        if (ind == -1) {
            Console.WriteLine(ind);
            return;
        }
  
        // Print largest non-repeating element
        Console.WriteLine(arr[ind]);
    }
      
    // Drivers Code
    public static void Main ()
    {
        int[] arr = { 3, 1, 8, 8, 4 };
        int N = arr.Length;
        LarUnEl(arr, N);
    }
  
}
 
// This code is contributed by susmitakundugoaldanga

<script>
 
 
// Javascript program to implement
// the above approach
 
// Function to find the largest unique
// element of the array
function LarUnEl(arr, N)
{
    // Store frequency of each
    // distinct array element
    var mp = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Update frequency of arr[i]
        if(mp.has(arr[i]))
            mp.set(arr[i], mp.get(arr[i])+1)
        else
            mp.set(arr[i], 1);
    }
 
    // Stores largest non-repeating
    // element present in the array
    var LNRElem = -1000000000;
 
    // Stores index of the largest
    // unique element of the array
    var ind = -1;
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // If frequency of arr[i] is equal
        // to 1 and arr[i] exceeds LNRElem
        if (mp.get(arr[i]) == 1
            && arr[i] > LNRElem) {
 
            // Update ind
            ind = i;
 
            // Update LNRElem
            LNRElem = arr[i];
        }
    }
 
    // If no array element is found
    // with frequency equal to 1
    if (ind == -1) {
        cout << ind;
        return;
    }
 
    // Print the largest
    // non-repeating element
    document.write( arr[ind]);
}
 
// Driver Code
var arr = [3, 1, 8, 8, 4 ];
var N = arr.length;
LarUnEl(arr, N);
 
 
 
</script>

4

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