C++ 프로그래밍, m개의 홀수를 갖는 하위 배열의 수 찾기

C++를 사용해 본 적이 있다면 하위 배열이 무엇인지, 얼마나 유용한지 알아야 합니다. 우리 모두는 C++에서 여러 수학 문제를 쉽게 해결할 수 있다는 것을 알고 있습니다. 따라서 이 글에서는 C++에서 이러한 하위 배열을 사용하여 M개의 홀수에 대한 완전한 정보를 찾는 방법을 설명합니다.

이 문제에서는 주어진 배열로 구성된 여러 하위 배열과 정수 m을 찾아야 합니다. 여기서 각 하위 배열은 정확히 m개의 홀수를 포함합니다. 다음은 이 접근 방식의 간단한 예입니다.

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

첫 번째 접근 방식

이 접근 방식에서는 가능한 모든 하위 배열이 지정된 배열에서 생성되고 각 하위 배열에 정확히 m개의 홀수가 있는지 확인됩니다. 이는 O(n²)의 시간 복잡도를 갖는 간단한 생성 및 조회 방법입니다.

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Output

Number of subarrays with n numbers are: 6

위의 코드 설명

이 코드에서는 중첩 루프를 사용하여 m개의 홀수 하위 배열을 찾고, 외부 루프는 "i"를 증가시키는 데 사용되며, 이는 각 배열을 처리하는 데 사용됩니다. 배열의 요소입니다.

내부 루프는 하위 배열을 찾고 홀수 카운터가 m에 도달할 때까지 요소를 처리하고, 발견된 각 하위 배열에 대한 결과 카운터 카운트를 증가시키고 마지막으로 카운트에 저장된 결과를 인쇄하는 데 사용됩니다.

두 번째 방법

또 다른 방법은 다음과 같습니다. "i"개의 홀수 접두사를 저장하는 배열을 만들고, 각 요소를 처리하고, 홀수가 발견될 때마다 홀수의 수를 증가시킵니다.

홀수의 개수가 m보다 크거나 같으면 접두사 배열의 (홀수 - m) 위치에 있는 숫자를 추가하세요.

홀수가 m보다 크거나 같게 되면 인덱스와 "odd - m" 숫자가 count 변수에 추가될 때까지 형성된 하위 배열의 수를 계산합니다. 각 요소가 처리된 후 결과는 count 변수에 저장됩니다.

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Output

Number of subarrays with n numbers are: 6

위 코드 설명

시작 값을 사용하여 배열 및 변수 초기화 ​​-

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

여기서 변수 n은 배열의 크기로, 변수 m은 홀수 개수로 초기화합니다. 을 찾고 있습니다. 가능한 하위 배열의 개수를 유지하기 위해 개수를 0으로 초기화하고, 홀수를 0으로 초기화하고, n + 1 0 크기의 prefix_array로 변수 n을 초기화합니다.

루프 이해

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

이 루프에서 우리는 prefix_array에 있습니다. [ ]는 홀수 인덱스에 값을 구현한 다음 홀수가 발견되면 홀수 변수를 증가시킵니다. 홀수 변수가 m보다 크거나 같을 때 인덱스까지 하위 배열의 수를 형성할 수 있음을 알 수 있습니다.

마지막으로 count 변수에 저장된 m개의 홀수 하위 배열 번호를 인쇄하고 출력을 얻습니다.

결론

이 기사에서는 두 가지 방법으로 m개의 홀수 하위 배열 수를 찾는 방법을 살펴보았습니다.

• 각 하위 배열을 생성하고 그 안에 m개의 홀수가 있는지 확인하고 각 하위 배열을 증가시킵니다. arrayfound 배열의 개수입니다. 이 코드의 시간 복잡도는 O(n2)입니다.

• 효율적인 방법은 배열의 각 요소를 반복하고 접두사 배열을 만든 다음 접두사 배열의 도움을 사용하는 것입니다. 이 코드의 시간 복잡도는 O(n)입니다.

이 기사가 문제와 해결책을 이해하는 데 도움이 되기를 바랍니다.

위 내용은 C++ 프로그래밍, m개의 홀수를 갖는 하위 배열의 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!