Adott egy tömbnek a feladat az, hogy megkeressük ennek a tömbnek három elemét úgy, hogy azok rendezett formában legyenek, azaz bármely három elemre a[i] a[j] és a[k] a következő összefüggést követik: a[i]< a[j] < a[k] ahol én< j < k . Ezt a problémát a segítségével kell megoldani állandó tér vagy nincs több hely.
Ez a probléma már megoldott lineáris időben lineáris tér használatával: Keressen egy 3-as méretű rendezett részsorozatot a Lineáris idő alatt
Példák:
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 Megoldás: A cél három elem megtalálása a b és c olyan hogy a< b < c és az elemeknek ugyanabban a sorrendben kell előfordulniuk a tömbben.
Megközelítés: A feladat három elem megtalálásával foglalkozik a b c ahol 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 (kicsi) a tömb legkisebb elemét és a második változót kell tárolnia nagy akkor lesz hozzárendelve egy érték, amikor már van egy kisebb érték a (kicsi) változó. Ez egy két változó párjának kialakításához vezet, amelyek a kívánt sorozat első két elemét alkotják. Hasonlóképpen, ha egy másik érték található a tömbben, amely akkor van hozzárendelve, amikor az első két változó már hozzá van rendelve, és kisebb, mint a jelenlegi elem, akkor a harmadik érték keresése befejeződik. Ezzel befejeződik az a b és c hármas úgy, hogy a< b < c in similar sequence to the array.
Algoritmus
- Hozzon létre három változót kicsi - Tárolja a legkisebb elemet nagy - a sorozat második elemét tárolja én - hurokszámláló
- Mozgás a bemeneti tömb mentén az elejétől a végéig.
- Ha a jelen elem kisebb vagy egyenlő, mint változó kicsi frissítse a változót.
- Különben, ha a jelen elem kisebb vagy egyenlő, mint változó nagy frissítse a változót. Tehát itt van egy pár (kicsi nagy) ebben a pillanatban hol kicsi< large és a kívánt sorrendben fordulnak elő.
- Ellenkező esetben, ha az előző két eset nem egyezik, szakítsa meg a hurkot, mivel kapunk egy párt, ahol a jelen elem nagyobb mindkét változónál kicsi és nagy . Tárolja az indexet változóban én .
- Ha nem találkoztunk a break utasítással, akkor garantáltan nem létezik ilyen triplet.
- Egyébként van egy hármas, amely megfelel a kritériumoknak, de a változó kicsi lehet, hogy új, kisebb értékre frissítették.
- Tehát járja be a tömböt az elejétől az i indexig.
- Adja hozzá újra a változót kicsi minden olyan elemhez, amely kisebb, mint nagy garantáltan létezik ilyen.
- Nyomtassa ki az értékeket kicsi nagy és i-edik tömbelem
Végrehajtás :
a hivatali idő kiszámítása excelbenC++
// 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>
Kimenet
5 7 8
Bonyolultsági elemzés:
Mivel a tömbön csak kétszer haladunk át az időbonyolítás O(2*n) ami egyenlő azzal On) .
Mivel csak három elemet tárolunk, a tér összetettsége állandó, ill O(1) .