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)
- Si el elemento en el índice de inicio no es igual a x, simplemente devuelva la respuesta que proviene 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