차례
문제 정책
"선형 시간에서 크기 3의 정렬 된 하위 시퀀스 찾기"문제는 정수 정렬. 문제 설명은 array [i] <array [k] <array [k] 및 i <j <k와 같은 방식으로 세 개의 숫자를 찾아야합니다.
예
arr[] = {11,34,2,5,1,7,4 }
2 5 7
설명
2는 5보다 작고 5는 7보다 작으며 인덱스가 서로보다 작습니다.
암호알고리즘
1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
1. Check if arr[i] is smaller or equal to arr[minimum], if true
1. Set minimum to i and small[i] to -1.
2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
1. Check if arr[i] is greater than or equal to arr[maximum], if true
1. Set maximum to i and great[i] to -1.
2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
1. Return
설명
우리는이 정렬 of 정수. 우리는 분류 주어진 배열의 하위 시퀀스. 정렬 된 하위 시퀀스에는 정렬 된 순서로 찾아야하는 세 개의 숫자가 포함되어 있으며 연속적이지 않고 연속적으로 있어야합니다. 첫 번째 숫자는 두 번째 숫자보다 작아야하고 두 번째 숫자는 세 번째 숫자보다 작아야합니다. 두 번째와 세 번째가 순서대로 와야합니다.
배열을 1에서 n 미만으로 순회 할 것입니다. 첫 번째와 마지막 인덱스 요소는 그대로 둡니다. 우리가 만든 두 개의 배열에서 작고 큰 -1을 표시했기 때문입니다. 우리는 그들의 첫 번째 요소를 표시했고 인덱스 요소는 각각 작은 배열과 큰 배열의 -1과 같습니다. 배열을 순회하고 arr [i]가 arr [minimum]보다 작거나 같은지 확인합니다. 여기서 최소값은 0으로 표시하고 조건이 참이면 최소값을 i로 업데이트하고 현재 작은 배열로 표시합니다. 요소를 -1로 설정합니다.
그레이트 배열에 대해서도 똑같이 할 것이지만, 오른쪽의 두 번째 요소에서 0으로 배열의 순회에서. 어레이를 순회하고 arr [i]가 arr [maximum보다 크거나 같은지 확인합니다. ], 그것이 참이면 최대 값을 0으로, great [i]를 -1로 업데이트해야합니다. 그렇지 않으면 최대 값을 크게 [i]로 설정합니다. 그런 다음 배열을 다시 탐색하고 small [i] 및 great [i]가 -1과 같지 않은지 확인하고 참이면 언급 된 값을 인쇄합니다.
암호
선형 시간에서 크기 3의 정렬 된 하위 시퀀스를 찾는 C ++ 코드
#include<iostream>
using namespace std;
void getTriplet(int arr[], int n)
{
int maximum = n - 1;
int minimum = 0;
int i;
int* small = new int[n];
small[0] = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}
int* great = new int[n];
great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}
for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
return;
}
}
cout << "3 numbers not found";
delete[] small;
delete[] great;
return;
}
int main()
{
int arr[] = { 11,34,2,5,1,7,4 };
int n = sizeof(arr) / sizeof(arr[0]);
getTriplet(arr, n);
return 0;
}
2 5 7
선형 시간에서 크기 3의 정렬 된 하위 시퀀스를 찾는 Java 코드
class SortedSubsequenceSize3
{
public static void getTriplet(int arr[])
{
int n = arr.length;
int maximum = n - 1;
int minimum = 0;
int i;
int[] small = new int[n];
small[0] = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}
int[] great = new int[n];
great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}
for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
return;
}
}
System.out.println("3 numbers not found");
return;
}
public static void main(String[] args)
{
int arr[] = { 11,34,2,5,1,7,4 };
getTriplet(arr);
}
}
2 5 7
복잡성 분석
시간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. 모든 배열 요소를 탐색했습니다. 그리고 배열의 크기가 N이기 때문입니다. 시간 복잡도도 선형입니다.
공간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. 우리는 각 배열 요소에 대해 더 작고 큰 요소를 저장했습니다. 따라서 공간 복잡성도 선형입니다.
