logo

TechCodeview

Zoradená podsekvencia veľkosti 3 v lineárnom čase s použitím konštantného priestoru

Úlohou daného poľa je nájsť tri prvky tohto poľa tak, aby boli zoradené, t. j. pre všetky tri prvky a[i] a[j] a a[k] platia tento vzťah: a[i]< a[j] < a[k] kde i< j < k . Tento problém je potrebné vyriešiť pomocou konštantný priestor alebo žiadny priestor navyše.

Tento problém je už vyriešený v lineárnom čase pomocou lineárneho priestoru: Nájdite zoradenú podsekvenciu veľkosti 3 v lineárnom čase

Príklady:  



  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

Riešenie: Cieľom je nájsť tri prvky a b a c také že a< b < c a prvky sa musia v poli vyskytovať v rovnakom poradí.

Prístup: Problém sa zaoberá hľadaním troch prvkov a b c, kde 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 (malý) by mal uchovávať najmenší prvok poľa a druhú premennú veľký bude priradená hodnota, keď už je prítomná menšia hodnota (malý) premenlivý. To povedie k vytvoreniu dvojice dvoch premenných, ktoré budú tvoriť prvé dva prvky požadovanej sekvencie. Podobne, ak je možné nájsť inú hodnotu v poli, ktoré je priradené, keď sú prvé dve premenné už priradené a má menšiu hodnotu ako prítomný prvok, hľadanie tretej hodnoty by bolo dokončené. Tým je trojica a b a c dokončená tak, že a< b < c in similar sequence to the array.

Algoritmus  

  1. Vytvorte tri premenné malý - Ukladá najmenší prvok veľký - uloží druhý prvok sekvencie i - počítadlo slučiek
  2. Pohybujte sa po vstupnom poli od začiatku do konca.
  3. Ak je prítomný prvok menší alebo rovný premennej malý aktualizovať premennú.
  4. Inak, ak je prítomný prvok menší alebo rovný premennej veľký aktualizovať premennú. Takže tu máme pár (malý veľký) v tejto chvíli kde malý< large a vyskytujú sa v požadovanom poradí.
  5. V opačnom prípade, ak sa predchádzajúce dva prípady nezhodujú, prerušte cyklus, pretože máme pár, v ktorom je prítomný prvok väčší ako obe premenné malý a veľký . Uložte index do premennej i .
  6. Ak sa príkaz break nenašiel, potom je zaručené, že takýto triplet neexistuje.
  7. V opačnom prípade trojica spĺňa kritériá, ale premenná malý mohla byť aktualizovaná na novú menšiu hodnotu.
  8. Prejdite teda pole od začiatku po index i.
  9. Znova priraďte premennú malý na akýkoľvek prvok menší ako veľký je zaručené, že taký existuje.
  10. Vytlačte hodnoty malý veľký a prvok poľa

Implementácia :

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>

Výstup 
5 7 8

Analýza zložitosti:  

    Časová zložitosť: O(n). 
    Keďže pole prechádza len dvakrát, je časová zložitosť O(2*n) čo sa rovná O(n) .Priestorová zložitosť: O(1). 
    Keďže sú uložené iba tri prvky, priestorová zložitosť je konštantná resp O(1) .