logo

TechCodeview

Seřazená podposloupnost velikosti 3 v lineárním čase pomocí konstantního prostoru

Úkolem daného pole je najít tři prvky tohoto pole tak, aby byly seřazené, tj. pro jakékoli tři prvky a[i] a[j] a a[k] platí tento vztah: a[i]< a[j] < a[k] kde i< j < k . Tento problém je nutné vyřešit pomocí konstantní prostor nebo žádný prostor navíc.

Tento problém je již vyřešen v lineárním čase pomocí lineárního prostoru: Najděte seřazenou podsekvenci o velikosti 3 v lineárním čase

Pří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

Řešení: Cílem je najít tři prvky a b a c takové, že A< b < c a prvky se musí v poli vyskytovat ve stejném pořadí.

Přístup: Problém se zabývá nalezením tří prvků 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 měl ukládat nejmenší prvek pole a druhou proměnnou velký bude přiřazena hodnota, pokud je již v souboru přítomna menší hodnota (malý) variabilní. To povede k vytvoření dvojice dvou proměnných, které budou tvořit první dva prvky požadované sekvence. Podobně, pokud lze v poli, které je přiřazeno, když jsou již přiřazeny první dvě proměnné, najít jinou hodnotu a má menší hodnotu než přítomný prvek, bude hledání třetí hodnoty dokončeno. Tím je trojice ab a c dokončena tak, že a< b < c in similar sequence to the array.

Algoritmus  

  1. Vytvořte tři proměnné malý - Uloží nejmenší prvek velký - uloží druhý prvek sekvence i - počítadlo smyček
  2. Pohybujte se po vstupním poli od začátku do konce.
  3. Pokud je přítomný prvek menší nebo roven proměnné malý aktualizovat proměnnou.
  4. Jinak, pokud je přítomný prvek menší nebo roven proměnné velký aktualizovat proměnnou. Takže tady máme pár (malý velký) v tuto chvíli kde malý< large a vyskytují se v požadovaném pořadí.
  5. V opačném případě, pokud se předchozí dva případy neshodují, přerušte smyčku, protože máme pár, kde je přítomný prvek větší než obě proměnné malý a velký . Uložte index do proměnné i .
  6. Pokud nebyl nalezen příkaz break, je zaručeno, že žádný takový triplet neexistuje.
  7. Jinak existuje triplet, který splňuje kritéria, ale proměnná malý mohla být aktualizována na novou menší hodnotu.
  8. Projděte tedy pole od začátku do indexu i.
  9. Znovu přiřaďte proměnnou malý na jakýkoli prvek menší než velký je zaručeno, že takový existuje.
  10. Vytiskněte hodnoty malý velký a prvek pole

Implementace :

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 složitosti:  

    Časová složitost: O(n). 
    Vzhledem k tomu, že pole se prochází pouze dvakrát, je časová složitost O(2*n) která se rovná Na) .Prostorová složitost: O(1). 
    Protože jsou uloženy pouze tři prvky, je prostorová složitost konstantní resp O(1) .