Având în vedere o matrice, sarcina este de a găsi trei elemente ale acestei matrice astfel încât să fie în formă sortată, adică pentru oricare trei elemente a[i] a[j] și a[k] urmează această relație: a[i]< a[j] < a[k] unde i< j < k . Această problemă trebuie rezolvată folosind spațiu constant sau fără spațiu suplimentar.
Această problemă este deja rezolvată în timp liniar folosind spațiu liniar: Găsiți o subsecvență sortată de dimensiunea 3 în timp liniar
Exemple:
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 Soluţie: Obiectivul este de a găsi trei elemente a b și c astfel încât o< b < c iar elementele trebuie să apară în aceeași succesiune în matrice.
Abordare: Problema tratează găsirea a trei elemente a b c unde 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 (mic) ar trebui să stocheze cel mai mic element al matricei și a doua variabilă mare i se va atribui o valoare atunci când există deja o valoare mai mică prezentă în (mic) variabilă. Aceasta va duce la formarea unei perechi de două variabile care vor forma primele două elemente ale secvenței necesare. În mod similar, dacă o altă valoare poate fi găsită în tabloul care este atribuită atunci când primele două variabile sunt deja atribuite și are o valoare mai mică decât elementul prezent, căutarea celei de-a treia valori ar fi completă. Aceasta completează tripletul a b și c astfel încât a< b < c in similar sequence to the array.
Algoritm
- Creați trei variabile mic - Stochează cel mai mic element mare - stochează al doilea element al secvenței i - contor de bucle
- Deplasați-vă de-a lungul matricei de intrare de la început până la sfârșit.
- Dacă elementul prezent este mai mic sau egal cu variabila mic actualizați variabila.
- Altfel, dacă elementul prezent este mai mic sau egal cu variabila mare actualizați variabila. Deci aici avem o pereche (mic mare) în acest moment unde mic< large și apar în ordinea necesară.
- Altfel, dacă cele două cazuri anterioare nu se potrivesc, întrerupeți bucla deoarece avem o pereche în care elementul prezent este mai mare decât ambele variabile mic şi mare . Stocați indicele în variabilă i .
- Dacă instrucțiunea break nu a fost întâlnită, atunci este garantat că nu există un astfel de triplet.
- Altfel, există un triplet care satisface criteriile, dar variabila mic ar fi putut fi actualizat la o nouă valoare mai mică.
- Deci, traversați matricea de la început până la indexul i.
- Reatribuiți variabila mic la orice element mai mic de mare este garantat că există unul.
- Tipăriți valorile mic mare și al-lea element de matrice
Implementarea :
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>
Ieșire
5 7 8
Analiza complexității:
Deoarece matricea este parcursă doar de două ori, complexitatea timpului este O(2*n) care este egal cu Pe) .
Deoarece sunt stocate doar trei elemente, complexitatea spațiului este constantă sau O(1) .