logo

TechCodeview

Subsecuencia ordenada de tamaño 3 en tiempo lineal usando espacio constante

Dada una matriz, la tarea es encontrar tres elementos de esta matriz de modo que estén ordenados, es decir, para tres elementos cualesquiera a[i] a[j] y a[k] siguen esta relación: ai]< a[j] < a[k] dónde i< j < k . Este problema debe resolverse utilizando espacio constante o ningún espacio extra.

Este problema ya está resuelto en tiempo lineal usando espacio lineal: Encuentre una subsecuencia ordenada de tamaño 3 en tiempo lineal

Ejemplos:  



  Input:   arr[] = {12 11 10 5 2 6 30}   Output:   5 6 30 or 2 6 30   Explanation:   Answer is 5 6 30 because 5 < 6 < 30 and they occur in this sequence in the array.   Input:   arr[] = {5 7 4 8}   Output:   5 7 8   Explanation:   Answer is 5 7 8 because 5 < 7 < 8 and they occur in the same sequence in the array

Solución: El objetivo es encontrar tres elementos. un segundo yc tal que a< b < c y los elementos deben aparecer en la misma secuencia en la matriz.

java len de matriz

Acercarse: El problema trata de encontrar tres elementos a b c donde a< b < c and they must appear in the same order as in the array. So the intuition at any step must be followed as such. One of the variable (pequeño) debe almacenar el elemento más pequeño de la matriz y la segunda variable grande Se le asignará un valor cuando ya haya un valor menor presente en el (pequeño) variable. Esto conducirá a la formación de un par de dos variables que formarán los dos primeros elementos de la secuencia requerida. De manera similar, si se puede encontrar otro valor en la matriz asignada cuando las dos primeras variables ya están asignadas y tiene un valor menor que el elemento actual, la búsqueda del tercer valor estaría completa. Esto completa el triplete a b y c tal que a< b < c in similar sequence to the array.

carácter java a cadena

Algoritmo  

  1. Crea tres variables pequeño - Almacena el elemento más pequeño grande - almacena el segundo elemento de la secuencia i - contador de bucle
  2. Muévase a lo largo de la matriz de entrada desde el principio hasta el final.
  3. Si el elemento presente es menor o igual a la variable pequeño actualizar la variable.
  4. De lo contrario, si el elemento actual es menor o igual a la variable grande actualizar la variable. Entonces aquí tenemos un par (pequeño grande) en este instante donde pequeño< large y ocurren en la secuencia requerida.
  5. De lo contrario, si los dos casos anteriores no coinciden, rompa el ciclo ya que tenemos un par donde el elemento presente es mayor que ambas variables. pequeño y grande . Almacenar el índice en variable. i .
  6. Si no se ha encontrado la declaración de interrupción, se garantiza que no existe dicho triplete.
  7. De lo contrario, hay un triplete que satisface los criterios pero la variable pequeño Es posible que se haya actualizado a un nuevo valor más pequeño.
  8. Entonces recorra la matriz desde el inicio hasta el índice i.
  9. Reasignar la variable pequeño a cualquier elemento menor que grande se garantiza que existe uno.
  10. imprimir los valores pequeño grande y i-ésimo elemento de matriz

Implementación :

C++ 
// C/C++ program to find a sorted sub-sequence of // size 3 using constant space #include    using namespace std; // A function to fund a sorted sub-sequence of size 3 void find3Numbers(int arr[] int n) {  // Initializing small and large(second smaller)  // by INT_MAX  int small = INT_MAX large = INT_MAX;  int i;  for (i = 0; i < n; i++)  {  // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];  // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];  // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }  if (i == n)  {  printf('No such triplet found');  return;  }  // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }  printf('%d %d %d' small large arr[i]);  return; } // Driver program to test above function int main() {  int arr[] = {5 7 4 8};  int n = sizeof(arr)/sizeof(arr[0]);  find3Numbers(arr n);  return 0; }
Java 
// Java program to find a sorted subsequence of // size 3 using constant space class GFG {  // A function to fund a sorted subsequence of size 3  static void find3Numbers(int arr[] int n)  {  // Initializing small and large(second smaller)  // by INT_MAX  int small = +2147483647 large = +2147483647;  int i;  for (i = 0; i < n; i++)  {  // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  System.out.print('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    System.out.print(small+' '+large+' '+arr[i]);  return;  }    // Driver program  public static void main(String arg[])  {  int arr[] = {5 7 4 8};  int n = arr.length;  find3Numbers(arr n);  } } // This code is contributed by Anant Agarwal.
Python3 
# Python3 program to find a sorted subsequence  # of size 3 using constant space # Function to fund a sorted subsequence of size 3 def find3Numbers(arr n): # Initializing small and large(second smaller) # by INT_MAX small = +2147483647 large = +2147483647 for i in range(n): # Update small for smallest value of array if (arr[i] <= small): small = arr[i] # Update large for second smallest value of # array after occurrence of small elif (arr[i] <= large): large = arr[i] # If we reach here we found 3 numbers in # increasing order : small large and arr[i] else: break if (i == n): print('No such triplet found') return # last and second last will be same but # first element can be updated retrieving  # first element by looping upto i for j in range(i + 1): if (arr[j] < large): small = arr[j] break print(small' 'large' 'arr[i]) return # Driver program arr= [5 7 4 8] n = len(arr) find3Numbers(arr n) # This code is contributed by Anant Agarwal.
C# 
// C# program to find a sorted sub-sequence of // size 3 using constant space using System; class GFG {    // A function to fund a sorted sub-sequence  // of size 3  static void find3Numbers(int []arr int n)  {    // Initializing small and large(second smaller)  // by INT_MAX  int small = +2147483647 large = +2147483647;  int i;  for (i = 0; i < n; i++)  {    // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  Console.Write('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (int j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    Console.Write(small + ' ' + large + ' ' + arr[i]);  return;  }    // Driver program  public static void Main()  {  int []arr = {5 7 4 8};  int n = arr.Length;  find3Numbers(arr n);  } } <br> // This code is contributed by nitin mittal
PHP 
 // PHP program to find a sorted  // subsequence of size 3 using  // constant space // A function to fund a sorted // subsequence of size 3 function find3Numbers($arr $n) { // Initializing small and  // large(second smaller) // by INT_MAX $small = PHP_INT_MAX; $large = PHP_INT_MAX; $i; for($i = 0; $i < $n; $i++) { // Update small for smallest // value of array if ($arr[$i] <= $small) $small = $arr[$i]; // Update large for second // smallest value of after  // occurrence of small else if ($arr[$i] <= $large) $large = $arr[$i]; // If we reach here we  // found 3 numbers in // increasing order :  // small large and arr[i] else break; } if ($i == $n) { echo 'No such triplet found'; return; } // last and second last will // be same but first // element can be updated  // retrieving first element // by looping upto i for($j = 0; $j <= $i; $j++) { if ($arr[$j] < $large) { $small = $arr[$j]; break; } } echo $small' ' $large' ' $arr[$i]; return; } // Driver Code $arr = array(5 7 4 8); $n = count($arr); find3Numbers($arr $n); // This code is contributed by anuj_67. ?>
JavaScript 
<script>  // JavaScript program to find a  // sorted sub-sequence of  // size 3 using constant space    // A function to fund a sorted sub-sequence  // of size 3  function find3Numbers(arr n)  {    // Initializing small and large(second smaller)  // by INT_MAX  let small = +2147483647 large = +2147483647;  let i;  for (i = 0; i < n; i++)  {    // Update small for smallest value of array  if (arr[i] <= small)  small = arr[i];    // Update large for second smallest value of  // array after occurrence of small  else if (arr[i] <= large)  large = arr[i];    // If we reach here we found 3 numbers in  // increasing order : small large and arr[i]  else  break;  }    if (i == n)  {  document.write('No such triplet found');  return;  }    // last and second last will be same but first  // element can be updated retrieving first element  // by looping upto i  for (let j = 0; j <= i; j++)  {  if (arr[j] < large)  {  small = arr[j];  break;  }  }    document.write(small + ' ' + large + ' ' + arr[i]);  return;  }    let arr = [5 7 4 8];  let n = arr.length;  find3Numbers(arr n);   </script>

Producción 
5 7 8

Análisis de complejidad:  

    Complejidad temporal: O(n). 
    Como la matriz se recorre sólo el doble, la complejidad del tiempo es O(2*n) que es igual a En) .Complejidad espacial: O(1). 
    Dado que solo se almacenan tres elementos, la complejidad del espacio es constante o O(1) .