배열이 주어지면 이 배열의 세 요소를 정렬된 형식으로 찾는 것이 임무입니다. 즉, 임의의 세 요소 a[i] a[j] 및 a[k]에 대해 다음 관계를 따릅니다. 일체 포함]< a[j] < a[k] 어디 나< j < k . 이 문제는 다음을 사용하여 해결해야 합니다. 일정한 공간 또는 추가 공간이 없습니다.
이 문제는 이미 선형 공간을 사용하여 선형 시간으로 해결되었습니다. 선형 시간에서 크기 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 해결책: 목표는 세 가지 요소를 찾는 것입니다 a b 그리고 c 그렇게 에이< b < c 요소는 배열에서 동일한 순서로 나타나야 합니다.
접근하다: 문제는 세 가지 요소 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 (작은) 배열의 가장 작은 요소와 두 번째 변수를 저장해야 합니다. 크기가 큰 이미 더 작은 값이 있는 경우 값이 할당됩니다. (작은) 변하기 쉬운. 이로 인해 필요한 시퀀스의 처음 두 요소를 형성하는 두 변수 쌍이 형성됩니다. 마찬가지로 처음 두 변수가 이미 할당되어 있고 현재 요소보다 작은 값을 가질 때 할당된 배열에서 다른 값을 찾을 수 있으면 세 번째 값에 대한 검색이 완료됩니다. 이는 a, b, c 세 개가 완성됩니다.< b < c in similar sequence to the array.
연산
- 변수 3개 생성 작은 - 가장 작은 요소를 저장합니다. 크기가 큰 - 시퀀스의 두 번째 요소를 저장합니다. 나 - 루프 카운터
- 입력 배열을 따라 처음부터 끝까지 이동합니다.
- 현재 요소가 변수보다 작거나 같은 경우 작은 변수를 업데이트합니다.
- 그렇지 않으면 현재 요소가 변수보다 작거나 같은 경우 크기가 큰 변수를 업데이트합니다. 그래서 여기 우리는 한 쌍을 얻습니다 (작다 크다) 지금 이 순간 어디서 작은< large 그리고 필요한 순서대로 발생합니다.
- 그렇지 않으면 이전 두 사례가 일치하지 않으면 현재 요소가 두 변수보다 큰 쌍을 얻었으므로 루프를 중단합니다. 작은 그리고 크기가 큰 . 인덱스를 변수에 저장 나 .
- 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
복잡성 분석:
배열이 두 배만 탐색되므로 시간 복잡도는 O(2*n) 이는 다음과 같다 에) .
3개의 요소만 저장되므로 공간 복잡도는 일정하거나 오(1) .