Pateikus masyvą, užduotis yra rasti tris šio masyvo elementus, kad jie būtų surūšiuoti, t. y. bet kokiems trims elementams a[i] a[j] ir a[k] jie atitiktų šį ryšį: a[i]< a[j] < a[k] kur i< j < k . Ši problema turi būti išspręsta naudojant pastovi erdvė arba be papildomos vietos.
Ši problema jau išspręsta tiesiniu laiku naudojant tiesinę erdvę: Raskite surūšiuotą 3 dydžio poseką tiesiniu laiku
Pavyzdžiai:
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 Sprendimas: Tikslas yra rasti tris elementus a b ir c toks kad a< b < c o elementai masyve turi atsirasti ta pačia seka.
Prieiga: Problema susijusi su trijų elementų a b c, kur 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 (mažas) turėtų saugoti mažiausią masyvo elementą ir antrąjį kintamąjį didelis bus priskirta reikšmė, kai jau yra mažesnė reikšmė (mažas) kintamasis. Taip bus suformuota dviejų kintamųjų pora, kuri sudarys pirmuosius du reikiamos sekos elementus. Panašiai, jei masyve galima rasti kitą reikšmę, kuri priskiriama, kai pirmieji du kintamieji jau priskirti ir turi mažesnę reikšmę nei dabartinis elementas, trečiosios reikšmės paieška būtų baigta. Tai užbaigia tripletą a b ir c taip, kad a< b < c in similar sequence to the array.
Algoritmas
- Sukurkite tris kintamuosius mažas - Saugo mažiausią elementą didelis - saugo antrąjį sekos elementą i - kilpų skaitiklis
- Eikite įvesties masyve nuo pradžios iki pabaigos.
- Jei esamasis elementas yra mažesnis arba lygus kintamajam mažas atnaujinti kintamąjį.
- Kitu atveju, jei esamas elementas yra mažesnis arba lygus kintamajam didelis atnaujinti kintamąjį. Taigi čia mes gauname porą (mažas didelis) šią akimirką kur mažas< large ir jie atsiranda reikiama seka.
- Kitu atveju, jei ankstesni du atvejai nesutampa, nutraukite kilpą, nes gauname porą, kurioje esamas elementas yra didesnis už abu kintamuosius mažas ir didelis . Išsaugokite indeksą kintamajame i .
- Jei lūžio sakinys nebuvo aptiktas, garantuojama, kad tokio tripleto nėra.
- Kitu atveju yra tripletas, kuris atitinka kriterijus, bet kintamasis mažas galėjo būti atnaujinta į naują mažesnę vertę.
- Taigi perkelkite masyvą nuo pradžios iki indekso i.
- Iš naujo priskirkite kintamąjį mažas bet kuriam elementui, mažesniam nei didelis garantuota, kad toks yra.
- Spausdinkite reikšmes mažas didelis ir i-asis masyvo elementas
Įgyvendinimas :
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>
Išvestis
5 7 8
Sudėtingumo analizė:
Kadangi masyvas perkeliamas tik du kartus, yra sudėtingesnis laikas O(2*n) kuri yra lygi O(n) .
Kadangi saugomi tik trys elementai, erdvės sudėtingumas yra pastovus arba O(1) .