Dots masīvs, uzdevums ir atrast trīs šī masīva elementus tā, lai tie būtu sakārtotā formā, t.i., jebkuriem trim elementiem a[i] a[j] un a[k] tie ievērotu šo attiecību: a[i]< a[j] < a[k] kur i< j < k . Šī problēma ir jāatrisina, izmantojot pastāvīga telpa vai nav papildu vietas.
Šī problēma jau ir atrisināta lineārajā laikā, izmantojot lineāro telpu: Atrodiet sakārtotu 3. izmēra apakšsekvenci lineārajā laikā
Piemēri:
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 Risinājums: Mērķis ir atrast trīs elementus a b un c tāds tāds a< b < c un elementiem masīvā ir jāatrodas tādā pašā secībā.
Austrālijas pilsētas
Pieeja: Problēma ir saistīta ar trīs elementu a b c atrašanu, 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 (mazs) jāsaglabā mazākais masīva elements un otrais mainīgais liels tiks piešķirta vērtība, ja jau ir mazāka vērtība (mazs) mainīgs. Tas novedīs pie divu mainīgo lielumu pāra veidošanās, kas veidos pirmos divus vajadzīgās secības elementus. Līdzīgi, ja masīvā var atrast citu vērtību, kas tiek piešķirta, kad pirmie divi mainīgie jau ir piešķirti, un tam ir mazāka vērtība nekā pašreizējam elementam, trešās vērtības meklēšana būtu pabeigta. Tas pabeidz tripletu a b un c tā, lai a< b < c in similar sequence to the array.
Java pārvērš veselu skaitli virknē
Algoritms
- Izveidojiet trīs mainīgos mazs - Saglabā mazāko elementu liels - saglabā secības otro elementu i - cilpu skaitītājs
- Pārvietojieties pa ievades masīvu no sākuma līdz beigām.
- Ja pašreizējais elements ir mazāks vai vienāds ar mainīgo mazs atjaunināt mainīgo.
- Citādi, ja pašreizējais elements ir mazāks vai vienāds ar mainīgo liels atjaunināt mainīgo. Tātad, šeit mēs iegūstam pāri (mazs liels) šajā mirklī kur mazs< large un tie notiek vajadzīgajā secībā.
- Citādi, ja iepriekšējie divi gadījumi nesakrīt, pārtrauciet cilpu, jo esam ieguvuši pāri, kur pašreizējais elements ir lielāks par abiem mainīgajiem mazs un liels . Saglabājiet indeksu mainīgajā i .
- Ja pārtraukuma paziņojums nav konstatēts, tiek garantēts, ka šāda tripleta nav.
- Citādi ir triplets, kas atbilst kritērijiem, bet mainīgais mazs iespējams, ir atjaunināta uz jaunu mazāku vērtību.
- Tātad šķērsojiet masīvu no sākuma līdz indeksam i.
- Atkārtoti piešķiriet mainīgo mazs uz jebkuru elementu, kas mazāks par liels tiek garantēts, ka tāds eksistē.
- Izdrukājiet vērtības mazs liels un i-tais masīva elements
Īstenošana :
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>
Izvade
5 7 8
Sarežģītības analīze:
Tā kā masīvs tiek šķērsots tikai divas reizes, ir laika sarežģītība O(2*n) kas ir vienāds ar O(n) .
Tā kā tiek saglabāti tikai trīs elementi, telpas sarežģītība ir nemainīga vai O(1) .