String más larga de arr[i], arr[arr[i]], .. sin repetición

Posted on by Rudeus Greyrat

Dada una array de tamaño n tal que los elementos de la array son distintos y están en el rango de 0 a n-1. Necesitamos encontrar la longitud de la string más larga {arr[i], arr[arr[i]], arr[arr[arr[i]]]……} tal que no se repita ningún elemento del conjunto.

Ejemplos: 

Input : arr[] = [5, 4, 0, 3, 1, 6, 2]
Output :4
Explanation:
The longest chain without repetition is
{arr[0], arr[5], arr[6], arr[2]} = {5, 6, 2, 0}


Input : arr[] = {1, 0, 4, 2, 3}
Output :3
Explanation:
The longest chain without repetition is
{arr[2], arr[4], arr[3]} = {4, 2, 3}

Una solución ingenua es encontrar la longitud de la string más larga a partir de cada elemento. Para realizar un seguimiento de los Nodes visitados, mantenga una array visitada y reinicie esta array cada vez que encuentre la string más larga de un elemento.

Una solución eficiente es atravesar cada índice y establecerlos como -1. Una vez que vemos un índice que hemos establecido como -1, sabemos que nos hemos encontrado con el mismo índice, por lo que nos detenemos y comparamos si el recuento actual es mayor que el máximo que hemos visto hasta ahora. Podemos hacer esta configuración a -1 en su lugar para que no sigamos revisando los mismos índices una y otra vez. La razón por la que esto funciona es porque, dado que cada número es distinto, siempre hay una sola forma de llegar a un índice en particular. Así que no importa en qué índice comience en el ciclo particular, siempre verá el mismo ciclo y, por lo tanto, el mismo recuento. Entonces, una vez que se visita un ciclo por completo, podemos omitir la verificación de todos los índices en este ciclo.

C++

// C++ program to find longest chain of
// arr[i], arr[arr[i]], arr[arr[arr[i]]]
// without repetition.
#include <iostream>
using namespace std;
 
void aNesting(int arr[], int start, int& max)
{
    // Local maximum
    int c_max = 0;
 
    // if current element is not visited then
    // increase c_max by one, set arr[start]
    // and change the start to current value.
    while (arr[start] != -1) {
        c_max++;
        int temp = arr[start];
        arr[start] = -1;
        start = temp;
    }
    
   // if local max is greater than global max
   // then update global maximum
   if (c_max > max) max = c_max;
}
 
int maxLength(int arr[], int n)
{
    int max = 0;
    for (int i = 0; i < n; i++) {
        aNesting(arr, i, max);
    }
    return max;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 4, 0, 3, 1, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxLength(arr, n);
    return 0;
}

Java

// Java program to find longest chain of
// arr[i], arr[arr[i]], arr[arr[arr[i]]]
// without repetition.
import java.util.*;
 
class solution
{
 
static int aNesting(int arr[], int start, int max)
{
    // Local maximum
    int c_max = 0;
 
    // if current element is not visited then
    // increase c_max by one, set arr[start]
    // and change the start to current value.
    while (arr[start] != -1)
    {
        c_max++;
        int temp = arr[start];
        arr[start] = -1;
        start = temp;
    }
     
// if local max is greater than global max
// then update global maximum
     if (c_max > max)
      max = c_max;
       
     return max;
  }
 
static int maxLength(int[] arr, int n)
{
    int max = 0,max1;
    for (int i = 0; i < n; i++)
    {
        max1 = aNesting(arr, i, max);
        if(max1>max)
         max = max1;
    }
    return max;
 }
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 5, 4, 0, 3, 1, 6, 2 };
    int n = arr.length;
    System.out.println(maxLength(arr, n));
}
}
 
// This code is contributed by
// Surendra_Gangwar

Python3

# Python 3 program to find longest chain
# of arr[i], arr[arr[i]], arr[arr[arr[i]]]
# without repetition.
def aNesting(arr,start, max):
     
    # Local maximum
    c_max = 0
 
    # if current element is not visited then
    # increase c_max by one, set arr[start]
    # and change the start to current value.
    while (arr[start] != -1):
        c_max += 1
        temp = arr[start]
        arr[start] = -1
        start = temp
     
    # if local max is greater than global
    # max then update global maximum
    if (c_max > max):
        max = c_max
         
    return max
 
def maxLength(arr, n):
    max = 0
    for i in range(0, n, 1):
        max__ = aNesting(arr, i, max)
        if (max__>max):
            max = max__
    return max__
 
# Driver code
if __name__ =='__main__':
    arr = [5, 4, 0, 3, 1, 6, 2]
    n = len(arr)
    print(maxLength(arr, n))
     
# This code is contributed by
# Shashank_Sharma

C#

// C# program to find longest chain of
// arr[i], arr[arr[i]], arr[arr[arr[i]]]
// without repetition.
using System;
 
class GFG
{
 
static int aNesting(int[] arr, int start, int max)
{
    // Local maximum
    int c_max = 0;
 
    // if current element is not visited then
    // increase c_max by one, set arr[start]
    // and change the start to current value.
    while (arr[start] != -1)
    {
        c_max++;
        int temp = arr[start];
        arr[start] = -1;
        start = temp;
    }
     
    // if local max is greater than global max
    // then update global maximum
    if (c_max > max)
    max = c_max;
     
    return max;
}
 
static int maxLength(int[] arr, int n)
{
    int max = 0, max1;
    for (int i = 0; i < n; i++)
    {
        max1 = aNesting(arr, i, max);
        if(max1>max)
        max = max1;
    }
    return max;
}
 
// Driver code
public static void Main()
{
    int[] arr = { 5, 4, 0, 3, 1, 6, 2 };
    int n = arr.Length;
    Console.WriteLine(maxLength(arr, n));
}
}
 
// This code is contributed by
// Akanksha Rai

PHP

<?php
// PHP program to find longest chain of
// arr[i], arr[arr[i]], arr[arr[arr[i]]]
// without repetition.
 
function aNesting($arr, $start, &$max)
{
    // Local maximum
    $c_max = 0;
 
    // if current element is not visited then
    // increase c_max by one, set arr[start]
    // and change the start to current value.
    while ($arr[$start] != -1)
    {
        $c_max++;
        $temp = $arr[$start];
        $arr[$start] = -1;
        $start = $temp;
    }
     
// if local max is greater than global
// max then update global maximum
if ($c_max > $max)
    $max = $c_max;
}
 
function maxLength($arr, $n)
{
    $max = 0;
    for ($i = 0; $i < $n; $i++)
    {
        aNesting($arr, $i, $max);
    }
    return $max;
}
 
// Driver code
$arr = array(5, 4, 0, 3, 1, 6, 2 );
$n = sizeof($arr);
echo maxLength($arr, $n);
 
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
 
// Javascript program to find longest chain of
// arr[i], arr[arr[i]], arr[arr[arr[i]]]
// without repetition.
function aNesting(arr, start, max)
{
     
    // Local maximum
    var c_max = 0;
 
    // If current element is not visited then
    // increase c_max by one, set arr[start]
    // and change the start to current value.
    while (arr[start] != -1)
    {
        c_max++;
        var temp = arr[start];
        arr[start] = -1;
        start = temp;
    }
     
    // If local max is greater than global
    // max then update global maximum
    if (c_max > max)
        max = c_max;
     
    return max;
}
 
function maxLength(arr, n)
{
    var max = 0, max1;
    for(var i = 0; i < n; i++)
    {
        max1 = aNesting(arr, i, max);
         
        if (max1 > max)
            max = max1;
    }
    return max;
}
 
// Driver code
var arr = [ 5, 4, 0, 3, 1, 6, 2 ];
var n = arr.length;
 
document.write(maxLength(arr, n));
 
// This code is contributed by bunnyram19
 
</script>
Producción: 

4

 

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

Publicación traducida automáticamente

Artículo escrito por Yogesh Shukla 1 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 *