配列が与えられた場合、タスクは、この配列の 3 つの要素がソートされた形式になるように検索することです。つまり、任意の 3 つの要素 a[i] a[j] および a[k] について、次の関係に従います。 a[i]< a[j] < a[k] どこ 私< j < k 。この問題は次を使用して解決する必要があります 一定の空間 または余分なスペースがありません。
フィボナッチコードJava
この問題は、線形空間を使用して線形時間ですでに解決されています。 線形時間でサイズ 3 のソートされたサブシーケンスを検索します。
例:
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 解決： 目的は 3 つの要素を見つけることです a b そしてc そのような ある< b < c また、要素は配列内で同じ順序で出現する必要があります。
アプローチ： この問題は、3 つの要素 a b c を見つけることを扱います。< 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 （小さい） 配列の最小要素と 2 番目の変数を格納する必要があります 大きい より小さい値が既に存在する場合、値が割り当てられます。 （小さい） 変数。これにより、必要なシーケンスの最初の 2 つの要素を形成する 2 つの変数のペアが形成されます。同様に、最初の 2 つの変数がすでに割り当てられているときに割り当てられた配列内で別の値が見つかり、その値が現在の要素よりも小さい場合、3 番目の値の検索は完了します。これにより、次のようなトリプレット a b および c が完成します。< b < c in similar sequence to the array.
.tostring java
アルゴリズム
- 3 つの変数を作成する 小さい - 最小の要素を格納します 大きい - シーケンスの 2 番目の要素を格納します 私 - ループカウンター
- 入力配列に沿って最初から最後まで移動します。
- 現在の要素が変数以下の場合 小さい 変数を更新します。
- それ以外の場合、現在の要素が変数以下の場合 大きい 変数を更新します。ここでペアを取得します (小 大) この瞬間どこで 小さい< large そしてそれらは必要な順序で発生します。
- それ以外の場合、前の 2 つのケースが一致しない場合は、現在の要素が両方の変数より大きいペアを取得したため、ループを中断します。 小さい そして 大きい 。インデックスを変数に格納する 私 。
- Break ステートメントに遭遇しなかった場合は、そのようなトリプレットが存在しないことが保証されます。
- それ以外の場合は、基準を満たすトリプレットがありますが、変数は 小さい 新しい小さい値に更新された可能性があります。
- したがって、配列を先頭からインデックス i まで走査します。
- 変数を再代入する 小さい より小さい任意の要素に 大きい 存在することが保証されています。
- 値を出力する 小さい 大きい そして i 番目の配列要素
実装 :
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>
出力
5 7 8
複雑さの分析:
配列は 2 回しか走査されないため、時間計算量は次のようになります。 O(2*n) に等しい の上） 。
3 つの要素のみが保存されるため、空間複雑度は一定であるか、 ○(1) 。
配列Javaを返す方法