C++를 사용하여 최소값과 최대값이 동일한 하위 배열의 수를 찾는 코드를 작성하세요.

이 기사에서는 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.

해결 방법

예를 들어, 배열의 크기와 동일한 최소 및 최대 요소를 사용하여 최소 개수의 하위 배열을 구성할 수 있다고 말할 수 있습니다. 연속된 숫자가 동일한 경우 하위 배열의 수가 더 커질 수 있습니다.

따라서 각 요소를 순회하여 연속된 숫자가 동일한지 확인하는 방법을 사용할 수 있습니다. 연속된 숫자가 동일한 경우 개수를 늘리면 내부 루프를 중단합니다.

내부 루프가 끝나거나 중단될 때마다 결과 변수가 증가하고 마지막으로 결과 변수가 표시됩니다.

p>

Example

#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;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

위 코드 설명

이 코드에서는 n개 이상의 하위 배열을 구성할 수 있으므로 배열의 크기, 결과 = n을 저장하기 위해 n 변수를 사용합니다. 그리고 같은 숫자로 계산된 개수입니다.

외부 루프는 배열의 각 요소를 처리하는 데 사용됩니다. 내부 루프는 인덱스 요소 뒤에 몇 개의 연속된 동일한 숫자가 있는지 찾는 데 사용되며 내부 루프의 끝에서는 결과 변수와 함께 count 변수를 증가시킵니다. 마지막으로 result 변수에 저장된 출력이 표시됩니다.

효율적인 방법

이 방법에서는 각 요소를 반복하고 각 요소에 대해 연속된 동일한 숫자가 몇 개 있는지 검색합니다. 동일한 숫자가 발견될 때마다 count 변수를 증가시키고, 다른 숫자가 발견되면 "n = n*(n+1)/2" 공식을 사용하여 얼마나 많은 하위 배열을 형성할 수 있는지 알아냅니다. 결과 변수를 증가시킵니다.

Example

#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;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

위의 코드 설명

이 코드에서는 임시 변수에 배열의 0번째 인덱스를 저장하고 인덱스 1부터 루프를 시작합니다. 임시 변수가 현재 인덱스의 요소와 같은지 확인하고 발견된 동일한 숫자에 대해 개수를 1씩 증가시킵니다. 임시 변수가 인덱스 요소와 같지 않으면 같은 수를 세어 파생할 수 있는 하위 배열의 조합을 찾아 그 결과를 결과 변수에 저장합니다. 임시 값을 현재 인덱스로 변경하고 개수를 1로 재설정합니다. 마지막으로 결과 변수에 저장된 답변을 표시합니다.

결론

이 글에서는 최소 요소와 최대 요소가 동일한 하위 배열의 개수를 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 최소값과 최대값이 동일한 하위 배열의 수를 찾는 코드를 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!