Programa recursivo para encontrar todos los índices de un número

Dada una array arr de tamaño N y un entero X . La tarea es encontrar todos los índices del entero X en la array
Ejemplos: 
 

Entrada: arr = {1, 2, 3, 2, 2, 5}, X = 2 
Salida: 1 3 4  El
elemento 2 está presente en los índices 1, 3, 4 (indexación basada en 0)
Entrada: arr[] = {7 , 7, 7}, X = 7 
Salida: 0 1 2 
 

El enfoque iterativo es simple, simplemente recorra la array dada y siga almacenando los índices del elemento en la otra array.
Enfoque recursivo
 

  • Si el índice de inicio alcanza la longitud de la array, devuelve una array vacía
  • De lo contrario, mantenga el primer elemento de la array consigo mismo y pase el resto de la array a la recursividad. 
    • Si el elemento en el índice de inicio no es igual a x, simplemente devuelva la respuesta que proviene de la recursividad. 
       
    • De lo contrario, si el elemento en el índice de inicio es igual a x, entonces cambie los elementos de la array (que es la respuesta de la recursividad) un paso a la derecha y luego coloque el índice de inicio al frente de la array (que vino a través de la recursividad) 
       

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

C++

// CPP program to find all indices of a number
#include <bits/stdc++.h>
using namespace std;
 
// A recursive function to find all
// indices of a number
int AllIndexesRecursive(int input[], int size,
                    int x, int output[])
{
     
    // If an empty array comes
    // to the function, then
    // return zero
    if (size == 0) {
        return 0;
    }
 
    // Getting the recursive answer
    int smallAns = AllIndexesRecursive(input + 1,
                                    size - 1, x, output);
 
    // If the element at index 0 is equal
    // to x then add 1 to the array values
    // and shift them right by 1 step
    if (input[0] == x) {
        for (int i = smallAns - 1; i >= 0; i--) {
            output[i + 1] = output[i] + 1;
        }
 
        // Put the start index in front
        // of the array
        output[0] = 0;
        smallAns++;
    }
    else {
         
        // If the element at index 0 is not equal
        // to x then add 1 to the array values
        for (int i = smallAns - 1; i >= 0; i--) {
            output[i] = output[i] + 1;
        }
    }
    return smallAns;
}
 
// Function to find all indices of a number
void AllIndexes(int input[], int n, int x)
{
    int output[n];
    int size = AllIndexesRecursive(input, n,
                                x, output);
    for (int i = 0; i < size; i++) {
        cout << output[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 2, 2, 5 }, x = 2;
     
    int n = sizeof(arr) / sizeof(arr[0]);
     
    // Function call
    AllIndexes(arr, n, x);
     
    return 0;
}

Java

// Java program to find all
// indices of a number
public class GFG {
 
    public int[] AllIndexesRecursive(int input[],
                                int x, int start)
    {
        // If the start index reaches the
        // length of the array, then
        // return empty array
        if (start == input.length) {
            int[] ans = new int[0]; // empty array
            return ans;
        }
 
        // Getting the recursive answer in
        // smallIndex array
        int[] smallIndex = AllIndexesRecursive(input, x,
                                              start + 1);
 
        // If the element at start index is equal
        // to x then
        // (which is the answer of recursion) and then
        // (which came through recursion)
        if (input[start] == x) {
            int[] myAns = new int[smallIndex.length + 1];
 
            // Put the start index in front
            // of the array
            myAns[0] = start;
            for (int i = 0; i < smallIndex.length; i++) {
                 
                // Shift the elements of the array
                // one step to the right
                // and putting them in
                // myAns array
                myAns[i + 1] = smallIndex[i];
            }
            return myAns;
        }
        else {
             
            // If the element at start index is not
            // equal to x then just simply return the
            // answer which came from recursion.
            return smallIndex;
        }
    }
 
    public int[] AllIndexes(int input[], int x)
    {
 
        return AllIndexesRecursive(input, x, 0);
    }
     
    // Driver Code
    public static void main(String args[])
    {
        GFG g = new GFG();
        int arr[] = { 1, 2, 3, 2, 2, 5 }, x = 2;
         
        int output[] = g.AllIndexes(arr, x);
         
        // Printing the output array
        for (int i = 0; i < output.length; i++) {
            System.out.print(output[i] + " ");
        }
    }
}

Python3

# Python3 program to find all
# indices of a number
def AllIndexesRecursive(input, x, start):
     
    # If the start index reaches the
    # length of the array, then
    # return empty array
    if (start == len(input)):
        ans = [] # empty array
        return ans
 
    # Getting the recursive answer in
    # smallIndex array
    smallIndex = AllIndexesRecursive(input, x,
                                     start + 1)
 
    # If the element at start index is equal
    # to x then
    # (which is the answer of recursion) and then
    # (which came through recursion)
    if (input[start] == x):
        myAns = [0 for i in range(len(smallIndex) + 1)]
 
        # Put the start index in front
        # of the array
        myAns[0] = start
        for i in range(len(smallIndex)):
 
            # Shift the elements of the array
            # one step to the right
            # and putting them in
            # myAns array
            myAns[i + 1] = smallIndex[i]
 
        return myAns
    else:
 
        # If the element at start index is not
        # equal to x then just simply return the
        # answer which came from recursion.
        return smallIndex
 
# Function to find all indices of a number
def AllIndexes(input, x):
 
    return AllIndexesRecursive(input, x, 0)
 
# Driver Code
arr = [ 1, 2, 3, 2, 2, 5 ]
x = 2
 
output=AllIndexes(arr, x)
 
# Printing the output array
for i in output:
    print(i, end = " ")
 
# This code is contributed by Mohit Kumar

C#

// C# program to find all
// indices of a number
using System;
class GFG
{
    public int[] AllIndexesRecursive(int []input,
                                        int x, int start)
    {
        // If the start index reaches the
        // length of the array, then
        // return empty array
        if (start == input.Length)
        {
            int[] ans = new int[0]; // empty array
            return ans;
        }
 
        // Getting the recursive answer in
        // smallIndex array
        int[] smallIndex = AllIndexesRecursive(input, x,
                                               start + 1);
 
        // If the element at start index is equal
        // to x then
        // (which is the answer of recursion) and
        // then (which came through recursion)
        if (input[start] == x)
        {
            int[] myAns = new int[smallIndex.Length + 1];
 
            // Put the start index in front
            // of the array
            myAns[0] = start;
            for (int i = 0; i < smallIndex.Length; i++)
            {
                 
                // Shift the elements of the array
                // one step to the right
                // and putting them in
                // myAns array
                myAns[i + 1] = smallIndex[i];
            }
            return myAns;
        }
        else
        {
             
            // If the element at start index is not
            // equal to x then just simply return the
            // answer which came from recursion.
            return smallIndex;
        }
    }
 
    public int[] AllIndexes(int []input, int x)
    {
        return AllIndexesRecursive(input, x, 0);
    }
     
    // Driver Code
    public static void Main()
    {
        GFG g = new GFG();
        int []arr = { 1, 2, 3, 2, 2, 5 };
        int x = 2;
         
        int []output = g.AllIndexes(arr, x);
         
        // Printing the output array
        for (int i = 0; i < output.Length; i++)
        {
            Console.Write(output[i] + " ");
        }
    }
}
 
// This code is contributed by anuj_67..

Javascript

<script>
    // Javascript program to find all indices of a number
     
    function AllIndexesRecursive(input, x, start)
    {
        // If the start index reaches the
        // length of the array, then
        // return empty array
        if (start == input.length)
        {
            let ans = new Array(0); // empty array
            return ans;
        }
   
        // Getting the recursive answer in
        // smallIndex array
        let smallIndex = AllIndexesRecursive(input, x, start + 1);
   
        // If the element at start index is equal
        // to x then
        // (which is the answer of recursion) and
        // then (which came through recursion)
        if (input[start] == x)
        {
            let myAns = new Array(smallIndex.length + 1);
   
            // Put the start index in front
            // of the array
            myAns[0] = start;
            for (let i = 0; i < smallIndex.length; i++)
            {
                   
                // Shift the elements of the array
                // one step to the right
                // and putting them in
                // myAns array
                myAns[i + 1] = smallIndex[i];
            }
            return myAns;
        }
        else
        {
               
            // If the element at start index is not
            // equal to x then just simply return the
            // answer which came from recursion.
            return smallIndex;
        }
    }
   
    function AllIndexes(input, x)
    {
        return AllIndexesRecursive(input, x, 0);
    }
     
    let arr = [ 1, 2, 3, 2, 2, 5 ];
    let x = 2;
 
    let output = AllIndexes(arr, x);
 
    // Printing the output array
    for(let i = 0; i < output.length; i++)
    {
      document.write(output[i] + " ");
    }
     
    // This code is contributed by mukesh07.
</script>
Producción

1 3 4 

Enfoque recursivo más simple: (atravesar desde el final)

  • Si el último índice alcanza la longitud de la array, devuelve una array vacía
  • De lo contrario, reduzca el último índice y pase toda la array a la recursividad.
  • Si el elemento en el último índice no es igual a x, simplemente devuelva la respuesta que proviene de la recursividad.
  • De lo contrario, si el elemento en el último índice es igual a x, simplemente inserte el último elemento en el último índice en el índice apuntado por ans.

Esto evita la complicación de desplazar todos los elementos por un índice y también incrementar todos los elementos en la array de salida.

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

C++

// CPP program to find all indices of a number
#include <bits/stdc++.h>
using namespace std;
 
// A recursive function to find all
// indices of a number
int AllIndexesRecursive(int input[], int size,
                    int x, int output[])
{
     
    // If the input array becomes empty
      if(size == 0)
        return 0;
 
         
    // Getting the recursive answer
      int smallAns = AllIndexesRecursive(input, size - 1, x, output);
     
      // If the last element of input array is equal to x
    if(input[size - 1] == x)
    {
      // Insert the index of last element of the input array into the output array
      // And increment ans
      output[smallAns++] = size - 1;
    }
    return smallAns;
}
 
// Function to find all indices of a number
void AllIndexes(int input[], int n, int x)
{
    int output[n];
    int size = AllIndexesRecursive(input, n,
                                x, output);
    for (int i = 0; i < size; i++) {
        cout << output[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 2, 2, 5 }, x = 2;
     
    int n = sizeof(arr) / sizeof(arr[0]);
     
    // Function call
    AllIndexes(arr, n, x);
     
    return 0;
}

Java

// Java program to find all indices of a number
public class Main
{
    // A recursive function to find all
    // indices of a number
    static int AllIndexesRecursive(int[] input, int size, int x, int[] output)
    {
          
        // If the input array becomes empty
          if(size == 0)
            return 0;
      
              
        // Getting the recursive answer
        int smallAns = AllIndexesRecursive(input, size - 1, x, output);
          
          // If the last element of input array is equal to x
        if(input[size - 1] == x)
        {
          // Insert the index of last element of the input array into the output array
          // And increment ans
          output[smallAns++] = size - 1;
        }
        return smallAns;
    }
      
    // Function to find all indices of a number
    static void AllIndexes(int[] input, int n, int x)
    {
        int[] output = new int[n];
        int size = AllIndexesRecursive(input, n, x, output);
        for (int i = 0; i < size; i++) {
            System.out.print(output[i] + " ");
        }
    }
     
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 2, 2, 5 };
        int x = 2;
          
        int n = arr.length;
          
        // Function call
        AllIndexes(arr, n, x);
    }
}
 
// This code is contributed by suresh07.

Python3

# Python3 program to find all indices of a number
 
# A recursive function to find all
# indices of a number
def AllIndexesRecursive(Input, size, x, output):
    # If the input array becomes empty
    if size == 0:
        return 0
    
    # Getting the recursive answer
    smallAns = AllIndexesRecursive(Input, size - 1, x, output)
        
    # If the last element of input array is equal to x
    if Input[size - 1] == x:
       
      # Insert the index of last element of the input array into the output array
      # And increment ans
      output[smallAns] = size - 1
      smallAns+=1
    return smallAns
    
# Function to find all indices of a number
def AllIndexes(Input, n, x):
    output = [0]*n
    size = AllIndexesRecursive(Input, n, x, output)
    for i in range(size):
        print(output[i], "", end = "")
 
arr = [ 1, 2, 3, 2, 2, 5 ]
x = 2
    
n = len(arr)
    
# Function call
AllIndexes(arr, n, x)
 
# This code is contributed by rameshtravel07

C#

// C# program to find all indices of a number
using System;
using System.Collections.Generic;
class GFG {
 
    // A recursive function to find all
    // indices of a number
    static int AllIndexesRecursive(int[] input, int size, int x, int[] output)
    {
          
        // If the input array becomes empty
          if(size == 0)
            return 0;
      
              
        // Getting the recursive answer
        int smallAns = AllIndexesRecursive(input, size - 1, x, output);
          
          // If the last element of input array is equal to x
        if(input[size - 1] == x)
        {
          // Insert the index of last element of the input array into the output array
          // And increment ans
          output[smallAns++] = size - 1;
        }
        return smallAns;
    }
      
    // Function to find all indices of a number
    static void AllIndexes(int[] input, int n, int x)
    {
        int[] output = new int[n];
        int size = AllIndexesRecursive(input, n, x, output);
        for (int i = 0; i < size; i++) {
            Console.Write(output[i] + " ");
        }
    }
 
  static void Main() {
    int[] arr = { 1, 2, 3, 2, 2, 5 };
    int x = 2;
      
    int n = arr.Length;
      
    // Function call
    AllIndexes(arr, n, x);
  }
}
 
// This code is contributed by decode22007.

Javascript

<script>
    // Javascript program to find all indices of a number
     
    // A recursive function to find all
    // indices of a number
    function AllIndexesRecursive(input, size, x, output)
    {
           
        // If the input array becomes empty
          if(size == 0)
            return 0;
       
               
        // Getting the recursive answer
        let smallAns = AllIndexesRecursive(input, size - 1, x, output);
           
          // If the last element of input array is equal to x
        if(input[size - 1] == x)
        {
          // Insert the index of last element of the input array into the output array
          // And increment ans
          output[smallAns++] = size - 1;
        }
        return smallAns;
    }
       
    // Function to find all indices of a number
    function AllIndexes(input, n, x)
    {
        let output = new Array(n);
        let size = AllIndexesRecursive(input, n, x, output);
        for (let i = 0; i < size; i++) {
            document.write(output[i] + " ");
        }
    }
     
    let arr = [ 1, 2, 3, 2, 2, 5 ];
    let x = 2;
       
    let n = arr.length;
       
    // Function call
    AllIndexes(arr, n, x);
 
// This code is contributed by divyeshrabadiya07.
</script>
Producción

1 3 4 

Publicación traducida automáticamente

Artículo escrito por Deepak_Malik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *