Gitt en matrise er oppgaven å finne tre elementer i denne matrisen slik at de er i sortert form, dvs. for alle tre elementer a[i] a[j] og a[k] følger de dette forholdet: a[i]< a[j] < a[k] hvor jeg< j < k . Dette problemet må løses ved hjelp av konstant plass eller ingen ekstra plass.
streng til json-objekt
Dette problemet er allerede løst i lineær tid ved å bruke lineært rom: Finn en sortert undersekvens av størrelse 3 i lineær tid
Eksempler:
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 Løsning: Målet er å finne tre elementer a b og c slik at en< b < c og elementene må forekomme i samme rekkefølge i matrisen.
Nærme: Oppgaven handler om å finne tre elementer a b c hvor 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 (liten) skal lagre det minste elementet i matrisen og den andre variabelen stor vil bli tildelt en verdi når det allerede er en mindre verdi tilstede i (liten) variabel. Dette vil føre til dannelsen av et par av to variabler som vil danne de to første elementene i den nødvendige sekvensen. Tilsvarende hvis en annen verdi kan bli funnet i matrisen som er tildelt når de to første variablene allerede er tildelt og har en mindre verdi enn det nåværende elementet, vil søket etter den tredje verdien være fullført. Dette fullfører tripletten a b og c slik at a< b < c in similar sequence to the array.
installer maven
Algoritme
- Lag tre variabler liten - Lagrer det minste elementet stor - lagrer det andre elementet i sekvensen jeg - loop teller
- Flytt langs inndatamatrisen fra start til slutt.
- Hvis det nåværende elementet er mindre enn eller lik variabel liten oppdater variabelen.
- Ellers hvis det nåværende elementet er mindre enn eller lik variabel stor oppdater variabelen. Så her får vi et par (liten stor) på dette øyeblikket hvor liten< large og de forekommer i ønsket rekkefølge.
- Ellers hvis de to foregående tilfellene ikke samsvarer, bryter vi løkken ettersom vi har et par der det nåværende elementet er større enn begge variablene liten og stor . Lagre indeksen i variabel jeg .
- Hvis bruddsetningen ikke har blitt funnet, er det garantert at det ikke eksisterer en slik triplett.
- Ellers er det en triplett som tilfredsstiller kriteriene, men variabelen liten kan ha blitt oppdatert til en ny mindre verdi.
- Så traverser matrisen fra start til indeks i.
- Tilordne variabelen på nytt liten til ethvert element mindre enn stor det er garantert at det finnes en.
- Skriv ut verdiene liten stor og matriseelementet
Implementering :
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>
Produksjon
5 7 8
Kompleksitetsanalyse:
Siden matrisen bare krysses to ganger så er tidskompleksiteten O(2*n) som er lik På) .
Siden bare tre elementer er lagret er romkompleksiteten konstant eller O(1) .
linux-filer