Cómo encontrar el último índice de un número en una array en C++

Dada una array arr[] de N enteros y el número K , la tarea es encontrar la última aparición de K en arr[] . Si el elemento no está presente, devuelve -1 .
Ejemplos: 

Entrada: arr[] = {1, 3, 4, 2, 1, 8}, K = 1 
Salida: 4 
Explicación: 
Hay dos ocurrencias de 1 en el índice 0 y 4. Pero la última ocurrencia está en el índice 4.
Entrada : arr[] = {3, 4, 5, 6, 7}, K = 2 
Salida: -1 
Explicación: 
Dado que 2 no está presente en la array. 

Método 1: Uso de la recursividad 

• Iterar recursivamente desde el último índice de la array dada: 
  • Caso base: si alcanzamos el índice inicial de forma recursiva, eso significa que el elemento K dado no está presente en la array.

if(idx < 0) {
  return -1;
}

• Declaración de devolución: si el elemento actual en la llamada recursiva es igual a K , devuelva el índice actual de la función.

if(arr[idx]==K) {
   return idx;
}

• Llamada recursiva: si el elemento en el índice actual no es igual a K , llame recursivamente para la próxima iteración.

return recursive_function(arr, idx - 1)

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the last
// index of the given number K
int findIndex(int arr[], int idx, int K)
{
 
    // Base Case
    if (idx < 0)
        return -1;
 
    // Return Statement
    if (arr[idx] == K) {
        return idx;
    }
 
    // Recursive Call
    return findIndex(arr, idx - 1, K);
}
 
// Driver Code
int main()
{
 
    int arr[] = { 3, 1, 4, 4, 2, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
 
    // Function call
    cout << findIndex(arr, N - 1, K);
 
    return 0;
}

3

Complejidad de tiempo: O(N), donde N es la longitud de la array.
Método 2: Usar la función incorporada find() y find_if() : 
La idea es encontrar el primer elemento desde el final de la array para encontrar el último elemento desde el principio de la array. A continuación se muestran los pasos: 

1. Invierte la array dada .
2. Encuentre el primer elemento con valor K en la array invertida usando la función find() .
3. si el iterador devuelto por la función de búsqueda apunta al final de la array, entonces el elemento no está presente en la array.
4. De lo contrario, use la función de distancia() para encontrar la posición (por ejemplo, pos ) de la K en esta array invertida.
5. Para obtener la distancia para el último índice de K en la array dada, imprima (N – pos – 1) .

A continuación se muestra la implementación del enfoque anterior:
Uso de find()

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
   
// Function to find the last index of
// the given number K
int findIndex(int arr[], int N, int K)
{
   
    // Reverse the given array arr[]
    reverse(arr, arr + N);
   
    // Find the first occurrence of K
    // in this reversed array
    auto it = find(arr, arr + N, K);
   
    // If the element is not present
    // then return "-1"
    if (it == arr + N) {
        return -1;
    }
   
    // Else return the index found
    return (N - distance(arr, it) - 1);
}
   
// Driver Code
int main()
{
   
    int arr[] = { 3, 1, 4, 4, 2, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
   
    // Function call
    cout << findIndex(arr, N, K);
   
    return 0;
}

Usando find_if()

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
   
// Comparator structure for finding
// index of element with value K
struct comparator {
   
    int elem;
    comparator(int const& i)
        : elem(i)
    {
    }
   
    bool operator()(int const& i)
    {
        return (i == elem);
    }
};
   
// Function to find the last index of
// the given number K
int findIndex(int arr[], int N, int K)
{
   
    // Reverse the given array arr[]
    reverse(arr, arr + N);
   
    // Find the first occurrence of K
    // in this reversed array
    auto it = find_if(arr, arr + N,
                      comparator(K));
   
    // If the element is not present
    // then return "-1"
    if (it == arr + N) {
        return -1;
    }
   
    // Else return the index found
    return (N - distance(arr, it) - 1);
}
   
// Driver Code
int main()
{
   
    int arr[] = { 3, 1, 4, 4, 2, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
   
    // Function call
    cout << findIndex(arr, N, K);
   
    return 0;
}

3

Complejidad de tiempo: O(N) , donde N es el número de elementos en la array dada.

Método 3: (Forma iterativa) 

Utilice un bucle para encontrar la última posición.

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

// CPP program for the above approach
#include <iostream>
using namespace std;
int findIndex(int arr[], int idx, int K)
{
     
    // Traversing the array from
    // last position
    for (int i = idx; i >= 0; i--) {
        if (arr[i] == K)
            return i;
    }
    return -1;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 3, 1, 4, 4, 2, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
 
    // Function call
    cout << findIndex(arr, N - 1, K);
    return 0;
}

Producción:

3