이 기사에서는 C++를 사용하여 최대 및 최소 요소가 동일한 부분 배열의 수를 찾는 문제를 해결할 것입니다. 다음은 문제의 예입니다 -
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same. 해결 방법 찾기
예제를 보면 최소 개수의 하위 배열이 배열의 크기와 동일한 최소 및 최대 요소로 구성될 수 있다고 말할 수 있습니다. 동일한 연속 번호가 있는 경우 하위 배열의 수는 더 많을 수 있습니다.
따라서 모든 요소를 살펴보고 연속된 숫자가 동일한지 확인하고 연속된 숫자가 같으면 카운트를 증가시키고 다른 숫자가 발견되면 내부 루프를 끊는 접근 방식을 적용할 수 있습니다.
결과 변수는 내부 루프가 종료되거나 중단될 때마다 결과 변수를 증가시키고 최종적으로 결과 변수의 결과를 표시합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count =0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i]==a[j])
count++;
else
break;
}
result+=count;
count =0;
}
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} 출력
Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n2).
위 코드 설명
이 코드에서 우리는 배열의 크기를 저장하기 위해 변수 n을 사용하고 있습니다. 결과 =n입니다. 왜냐하면 동일한 숫자의 개수를 유지하기 위해 최소 n개의 하위 배열이 형성되고 계산될 수 있기 때문입니다.
외부 루프는 배열의 모든 요소를 처리하는 데 사용됩니다. 내부 루프는 인덱스 요소 뒤에 몇 개의 연속 숫자가 동일한지 찾고 내부 루프가 끝날 때마다 count 변수로 결과 변수를 증가시키는 데 사용됩니다. 마지막으로 결과 변수에 저장된 출력을 보여줍니다.
효율적인 접근
이 접근 방식에서는 모든 요소를 살펴보고 모든 요소에 대해 연속적으로 동일한 숫자가 몇 개 있는지 검색합니다. 동일한 숫자가 발견될 때마다 count 변수를 증가시키고 다른 숫자가 발견되면 count의 도움으로 "n =n*(n+1) 공식을 사용하여 구성할 수 있는 하위 배열 수를 찾습니다. /2" 이 공식의 답으로 결과 변수를 증가시킵니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count =1,temp=a[0];
for (int i = 1; i < n; i++) {
if (temp==a[i]){
count++;
}
else{
temp=a[i];
result = result + (count*(count+1)/2);
count=1;
}
}
result = result + (count*(count+1)/2);
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} 출력
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
위 코드 설명
이 코드에서는 배열의 0번째 인덱스를 temp 변수에 저장하고 인덱스 1로 루프를 시작합니다. temp 변수가 현재 인덱스의 요소와 같은지 확인하고 동일한 숫자가 발견되면 count를 1씩 증가시킵니다. 임시 변수가 인덱스 요소와 같지 않으면 동일한 숫자의 개수와 결과 변수에 결과를 저장하여 만들 수 있는 하위 배열의 조합을 찾습니다. temp 값을 현재 인덱스로 변경하여 count를 1로 재설정합니다. 마지막으로 결과 변수에 저장된 답을 보여줍니다.
결론
이 기사에서는 최소 및 최대 요소가 동일한 하위 배열의 수를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(보통 및 효율적)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.