Kun taulukko on annettu, tehtävänä on löytää tästä taulukosta kolme elementtiä siten, että ne ovat lajiteltuina, eli mille tahansa kolmelle elementille a[i] a[j] ja a[k] ne noudattavat tätä suhdetta: a[i]< a[j] < a[k] jossa i< j < k . Tämä ongelma on ratkaistava käyttämällä jatkuva tila tai ei ylimääräistä tilaa.
Tämä ongelma on jo ratkaistu lineaarisessa ajassa lineaarista tilaa käyttäen: Etsi lajiteltu alisarja, jonka koko on 3 lineaarisessa ajassa
Esimerkkejä:
skanneri skannaus java
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 Ratkaisu: Tavoitteena on löytää kolme elementtiä a b ja c sellasta a< b < c ja elementtien tulee esiintyä samassa järjestyksessä taulukossa.
Lähestyä: Tehtävänä on löytää kolme elementtiä a b c, joissa 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 (pieni) tulee tallentaa taulukon pienin elementti ja toinen muuttuja suuri määritetään arvo, kun arvossa on jo pienempi arvo (pieni) muuttuja. Tämä johtaa kahden muuttujan parin muodostumiseen, jotka muodostavat vaaditun sekvenssin kaksi ensimmäistä elementtiä. Vastaavasti, jos taulukosta löytyy toinen arvo, joka määritetään, kun kaksi ensimmäistä muuttujaa on jo määritetty ja jonka arvo on pienempi kuin nykyinen elementti, kolmannen arvon haku olisi valmis. Tämä täydentää tripletin a b ja c siten, että a< b < c in similar sequence to the array.
rom
Algoritmi
- Luo kolme muuttujaa pieni - Tallentaa pienimmän elementin suuri - tallentaa sekvenssin toisen elementin i - silmukkalaskuri
- Siirry syöttötaulukkoa pitkin alusta loppuun.
- Jos nykyinen elementti on pienempi tai yhtä suuri kuin muuttuja pieni päivittää muuttuja.
- Muuten, jos nykyinen elementti on pienempi tai yhtä suuri kuin muuttuja suuri päivittää muuttuja. Joten tässä saamme parin (pieni iso) tällä hetkellä missä pieni< large ja ne tapahtuvat vaaditussa järjestyksessä.
- Muutoin jos kaksi edellistä tapausta eivät täsmää, katkaise silmukka, koska meillä on pari, jossa nykyinen elementti on suurempi kuin molemmat muuttujat pieni ja suuri . Tallenna indeksi muuttujaan i .
- Jos break-lausetta ei ole kohdattu, on taattu, että sellaista triplettiä ei ole olemassa.
- Muutoin on kriteerit täyttävä tripletti, mutta muuttuja pieni on ehkä päivitetty uuteen pienempään arvoon.
- Joten käy läpi taulukon alusta indeksiin i.
- Määritä muuttuja uudelleen pieni mihin tahansa elementtiin, joka on pienempi kuin suuri on taattu, että sellainen on olemassa.
- Tulosta arvot pieni suuri ja i. taulukkoelementti
Toteutus :
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>
Lähtö
5 7 8
Monimutkaisuusanalyysi:
Koska matriisi kulkee vain kaksi kertaa niin monimutkainen kuin aika O(2*n) joka on yhtä suuri kuin O(n) .
Koska vain kolme elementtiä on tallennettu, tilan monimutkaisuus on vakio tai O(1) .