Bir dizi verildiğinde görev, bu dizinin üç öğesini sıralanmış biçimde olacak şekilde bulmaktır, yani herhangi üç öğe için a[i] a[j] ve a[k] bu ilişkiyi takip ederler: bir[i]< a[j] < a[k] Neresi Ben< j < k . Bu problem kullanılarak çözülmelidir. sabit alan veya ekstra alan yok.
dizeye Java tarihi
Bu problem zaten doğrusal uzay kullanılarak doğrusal zamanda çözülmüştür: Doğrusal Zamanda boyutu 3 olan sıralanmış bir alt dizi bulun
Örnekler:
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 Çözüm: Amaç üç element bulmaktır bir b ve c Öyle ki A< b < c ve elemanların dizide aynı sırada yer alması gerekir.
Yaklaşmak: Problem, a b c olmak üzere üç öğenin bulunmasıyla ilgilidir.< 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 (küçük) dizinin en küçük elemanını ve ikinci değişkeni saklamalıdır büyük zaten daha küçük bir değer mevcut olduğunda bir değer atanacaktır. (küçük) değişken. Bu, gerekli dizinin ilk iki elemanını oluşturacak iki değişken çiftinin oluşmasına yol açacaktır. Benzer şekilde, ilk iki değişken zaten atandığında atanan dizide mevcut elemandan daha küçük bir değere sahip başka bir değer bulunabilirse üçüncü değerin aranması tamamlanmış olacaktır. Bu, a b ve c üçlüsünü tamamlar, öyle ki a< b < c in similar sequence to the array.
java'da arraylist
Algoritma
- Üç değişken oluşturun küçük - En küçük elemanı saklar büyük - dizinin ikinci elemanını saklar Ben - döngü sayacı
- Giriş dizisi boyunca baştan sona ilerleyin.
- Mevcut eleman değişkenden küçük veya ona eşitse küçük değişkeni güncelleyin.
- Aksi takdirde mevcut öğe değişkenden küçük veya ona eşitse büyük değişkeni güncelleyin. Yani burada bir çift alıyoruz (küçük büyük) şu anda nerede küçük< large ve gerekli sırayla meydana gelirler.
- Aksi takdirde, eğer önceki iki durum eşleşmezse döngüyü kırın çünkü elimizde mevcut elemanın her iki değişkenden de büyük olduğu bir çift var küçük Ve büyük . Dizini değişkende saklayın Ben .
- Eğer break deyimiyle karşılaşılmamışsa, böyle bir üçlünün var olmadığı garanti edilir.
- Aksi takdirde kriterleri karşılayan bir üçlü vardır ancak değişken küçük yeni, daha küçük bir değere güncellenmiş olabilir.
- Yani diziyi baştan indeks i'ye kadar çaprazlayın.
- Değişkeni yeniden atayın küçük daha az herhangi bir elemente büyük birinin var olduğu garanti edilir.
- Değerleri yazdır küçük büyük ve dizi elemanı
Uygulama :
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>
Çıkış
5 7 8
Karmaşıklık Analizi:
Dizi yalnızca iki kez geçildiğinden zaman karmaşıklığı artar Ç(2*n) hangisi eşittir Açık) .
Yalnızca üç öğe depolandığından uzay karmaşıklığı sabittir veya Ç(1) .
yay modülleri