logo

TechCodeview

Subseqüència ordenada de mida 3 en temps lineal utilitzant espai constant

Donada una matriu, la tasca és trobar tres elements d'aquesta matriu de manera que estiguin en forma ordenada, és a dir, per a tres elements qualsevol a[i] a[j] i a[k] segueixen aquesta relació: a[i]< a[j] < a[k] on i< j < k . Aquest problema s'ha de resoldre utilitzant espai constant o sense espai addicional.

Aquest problema ja està resolt en temps lineal utilitzant l'espai lineal: Trobeu una subseqüència ordenada de mida 3 en temps lineal

Exemples:  



edat de vicky kaushal 
  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ó: L'objectiu és trobar tres elements a b i c tal que a< b < c i els elements s'han de presentar en la mateixa seqüència a la matriu.

Enfocament: El problema tracta de trobar tres elements a b c on 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 (petit) hauria d'emmagatzemar l'element més petit de la matriu i la segona variable gran s'assignarà un valor quan ja hi hagi un valor més petit present al (petit) variable. Això conduirà a la formació d'un parell de dues variables que formaran els dos primers elements de la seqüència requerida. De la mateixa manera, si es pot trobar un altre valor a la matriu que s'assigna quan les dues primeres variables ja estan assignades i té un valor més petit que l'element actual, la cerca del tercer valor seria completa. Això completa el triplet a b i c de manera que a< b < c in similar sequence to the array.

gestor de tasques linux

Algorisme  

  1. Crea tres variables petit - Emmagatzema l'element més petit gran - emmagatzema el segon element de la seqüència i - comptador de bucles
  2. Mou-te per la matriu d'entrada des del principi fins al final.
  3. Si l'element actual és menor o igual a variable petit actualitzar la variable.
  4. En cas contrari, si l'element actual és menor o igual a la variable gran actualitzar la variable. Així que aquí en tenim un parell (petit gran) en aquest instant on petit< large i es produeixen en la seqüència requerida.
  5. En cas contrari, si els dos casos anteriors no coincideixen, trenca el bucle ja que tenim un parell on l'element actual és més gran que ambdues variables petit i gran . Emmagatzema l'índex a la variable i .
  6. Si no s'ha trobat la instrucció break, es garanteix que no existeix aquest triplet.
  7. En cas contrari, hi ha un triplet que satisfà els criteris però la variable petit podria haver-se actualitzat a un nou valor més petit.
  8. Per tant, travessa la matriu des de l'inici fins a l'índex i.
  9. Torneu a assignar la variable petit a qualsevol element inferior a gran està garantit que n'hi ha un.
  10. Imprimeix els valors petit gran i el seu element de matriu

Implementació :

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>

Sortida 
5 7 8

Anàlisi de complexitat:  

    Complexitat temporal: O(n). 
    Com que la matriu es recorre només el doble de la complexitat del temps O(2*n) que és igual a O(n) .Complexitat espacial: O(1). 
    Com que només s'emmagatzemen tres elements la complexitat espacial és constant o O(1) .