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² ).

예시

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

출력

Number of subarrays with n numbers are: 6

위 코드 설명

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

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

두 번째 접근 방식

또 다른 접근법은 "i" 홀수가 있는 접두사 수를 저장하기 위한 배열을 만들고 모든 요소를 처리하고 발견된 모든 홀수에 대해 홀수 수를 늘리는 것입니다.

홀수의 개수가 m보다 크거나 같을 때 접두어 배열의 (odd - m ) 위치에 숫자를 추가합니다.

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

예시

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

출력

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으로 초기화합니다.

루프 이해

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보다 크거나 같을 때 인덱스까지 구성할 수 있는 하위 배열의 수를 찾습니다.

마지막으로, 카운트 변수에 저장된 m개의 홀수를 가진 다수의 하위 배열을 인쇄하고 출력을 얻습니다.

결론

이 기사에서는 두 가지 접근 방식에서 m개의 홀수가 있는 부분 배열의 수를 찾는 접근 방식을 이해합니다 -

모든 하위 배열을 생성하고 그 안에 있는 m개의 홀수를 확인하고 발견된 각 하위 배열의 개수를 늘립니다. 이 코드의 시간 복잡도는 O(n2)입니다.
배열의 각 요소를 살펴보고 접두사 배열을 만들고 접두사 배열을 사용하여 결과를 찾는 효율적인 접근 방식입니다. 이 코드의 시간 복잡도는 O(n)입니다.

이 문서가 문제와 솔루션을 이해하는 데 도움이 되기를 바랍니다.