Último elemento de array visto (la última aparición es la más temprana)

Dada una array que podría contener duplicados, encuentre el elemento cuya última aparición es la más reciente.

Ejemplos: 

Input :  arr[] = {10, 30, 20, 10, 20}
Output : 30
Explanation: Below are indexes of last
appearances of all elements (0 based indexes)
10 last occurs at index 3
30 last occurs at index 1
20 last occurs at index 2
The element whose last appearance earliest
is 30.

Input : arr[] = {20, 10, 20, 20, 40, 10}
Output : 20
Explanation: 
Explanation: Below are indexes of last
appearances of all elements (0 based indexes)
20 last occurs at index 2
10 last occurs at index 5
40 last occurs at index 4
The element whose last appearance earliest
is 20.

Un enfoque ingenuo es tomar cada elemento e iterar y comparar su última aparición con otros elementos. Esto requiere dos bucles anidados y tomará un tiempo O(n*n). 

Un enfoque eficiente es usar hashing. Almacenamos el índice de cada elemento donde ocurrió por última vez, y luego iteramos a través de todos los elementos posibles e imprimimos el elemento con la menor aparición de índice almacenado, ya que será el que se vio por última vez al atravesar de izquierda a derecha. 

Implementación:

// C++ program to find last seen element in
// an array.
#include <bits/stdc++.h>
using namespace std;
 
// Returns last seen element in arr[]
int lastSeenElement(int a[], int n)
{
    // Store last occurrence index of
    // every element
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++)
        hash[a[i]] = i;
 
    // Find an element in hash with minimum
    // index value
    int res_ind = INT_MAX, res;
    for (auto x : hash)
    {
       if (x.second < res_ind)
       {
            res_ind = x.second;
            res = x.first;
       }
    }
 
    return res;
}
 
// driver program
int main()
{
    int a[] = { 2, 1, 2, 2, 4, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << lastSeenElement(a, n);
    return 0;
}

// Java program to find last seen element in
// an array.
import java.util.*;
 
class GFG
{
 
// Returns last seen element in arr[]
static int lastSeenElement(int a[], int n)
{
    // Store last occurrence index of
    // every element
    HashMap<Integer,
            Integer> hash = new HashMap<Integer,       
                                        Integer>();
    for (int i = 0; i < n; i++)
    {
        hash.put(a[i], i);
    }
 
    // Find an element in hash with minimum
    // index value
    int res_ind = Integer.MAX_VALUE, res = 0;
    for (Map.Entry<Integer,
                   Integer> x : hash.entrySet())
    {
        if (x.getValue() < res_ind)
        {
            res_ind = x.getValue();
            res = x.getKey();
        }  
    }
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 2, 1, 2, 2, 4, 1 };
    int n = a.length;
    System.out.println(lastSeenElement(a, n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to find last seen
# element in an array.
import sys;
 
# Returns last seen element in arr[]
def lastSeenElement(a, n):
     
    # Store last occurrence index of
    # every element
    hash = {}
     
    for i in range(n):
        hash[a[i]] = i
         
    # Find an element in hash with minimum
    # index value
    res_ind = sys.maxsize
    res = 0
     
    for x, y in hash.items():
        if y < res_ind:
            res_ind = y
            res = x
             
    return res
 
# Driver code   
if __name__=="__main__":
     
    a = [ 2, 1, 2, 2, 4, 1 ]
    n = len(a)
     
    print(lastSeenElement(a,n))
 
# This code is contributed by rutvik_56

// C# program to find last seen element in
// an array.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Returns last seen element in arr[]
static int lastSeenElement(int []a, int n)
{
    // Store last occurrence index of
    // every element
    Dictionary<int,
               int> hash = new Dictionary<int,
                                          int>();
    for (int i = 0; i < n; i++)
    {
        if(hash.ContainsKey(a[i]))
        {
            hash[a[i]] = i;
        }
        else
        {
            hash.Add(a[i], i);
        }
    }
 
    // Find an element in hash with minimum
    // index value
    int res_ind = int.MaxValue, res = 0;
    foreach(KeyValuePair<int, int> x in hash)
    {
        if (x.Value < res_ind)
        {
            res_ind = x.Value;
            res = x.Key;
        }
    }
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = { 2, 1, 2, 2, 4, 1 };
    int n = a.Length;
    Console.WriteLine(lastSeenElement(a, n));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to find last seen element in
// an array.
 
 
// Returns last seen element in arr[]
function lastSeenElement(a, n)
{
    // Store last occurrence index of
    // every element
    let hash = new Map();
    for (let i = 0; i < n; i++)
    {
        hash.set(a[i], i);
    }
 
    // Find an element in hash with minimum
    // index value
    let res_ind = Number.MAX_SAFE_INTEGER, res = 0;
    for (let x of hash)
    {
        if (x[1] < res_ind)
        {
            res_ind = x[1];
            res = x[0];
        }
    }
    return res;
}
 
// Driver Code
 
    let a = [ 2, 1, 2, 2, 4, 1 ];
    let n = a.length;
    document.write(lastSeenElement(a, n));
 
 
// This code is contributed by gfgking
 
</script>

Producción:  

2

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