Étant donné un tableau, la tâche est de trouver trois éléments de ce tableau tels qu'ils soient sous forme triée, c'est-à-dire que pour trois éléments a[i] a[j] et a[k] ils suivent cette relation : un[je]< a[j] < a[k] où je< j < k . Ce problème doit être résolu en utilisant espace constant ou pas d'espace supplémentaire.
Ce problème est déjà résolu en temps linéaire en utilisant l'espace linéaire : Trouver une sous-séquence triée de taille 3 en temps linéaire
Exemples :
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 Solution: L'objectif est de trouver trois éléments un b et c tel que un< b < c et les éléments doivent apparaître dans la même séquence dans le tableau.
Approche: Le problème consiste à trouver trois éléments a b c où 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) doit stocker le plus petit élément du tableau et la deuxième variable grand se verra attribuer une valeur lorsqu'il y a déjà une valeur plus petite présente dans le (petit) variable. Cela conduira à la formation d’une paire de deux variables qui formeront les deux premiers éléments de la séquence requise. De même, si une autre valeur peut être trouvée dans le tableau attribué alors que les deux premières variables sont déjà affectées et a une valeur inférieure à l'élément actuel, la recherche de la troisième valeur serait terminée. Ceci complète le triplet a b et c tel que a< b < c in similar sequence to the array.
Algorithme
- Créer trois variables petit - Stocke le plus petit élément grand - stocke le deuxième élément de la séquence je - compteur de boucles
- Déplacez-vous le long du tableau d’entrée du début à la fin.
- Si l'élément présent est inférieur ou égal à la variable petit mettre à jour la variable.
- Sinon, si l'élément présent est inférieur ou égal à la variable grand mettre à jour la variable. Donc ici, nous obtenons une paire (petit grand) à cet instant où petit< large et ils se produisent dans l’ordre requis.
- Sinon, si les deux cas précédents ne correspondent pas, rompez la boucle car nous avons une paire où l'élément présent est supérieur aux deux variables. petit et grand . Stocker l'index dans une variable je .
- Si l'instruction break n'a pas été rencontrée, il est garanti qu'aucun triplet de ce type n'existe.
- Sinon il y a un triplet qui satisfait aux critères mais la variable petit pourrait avoir été mis à jour vers une nouvelle valeur plus petite.
- Parcourez donc le tableau du début à l’index i.
- Réaffecter la variable petit à tout élément inférieur à grand il est garanti qu'il en existe un.
- Imprimer les valeurs petit grand et le ième élément du tableau
Mise en œuvre :
C++// C/C++ program to find a sorted sub-sequence of // size 3 using constant space #include
// 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 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# 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 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. ?> <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>
Sortir
5 7 8
Analyse de complexité :
Comme le tableau n'est parcouru que deux fois, la complexité temporelle est O(2*n) qui est égal à Sur) .
Puisque seuls trois éléments sont stockés, la complexité de l'espace est constante ou O(1) .