使用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，為每個找到的子數組增加結果計數器計數，最後打印計數中存儲的結果

第二種方法

另一種方法是建立一個陣列來儲存「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 的prefix_array 初始化變數n 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 時，可以形成子數組的數量，直到索引。

最後，我們印出 count 變數中儲存的 m 個奇數的子數組數，並且得到輸出。

結論

在本文中，我們透過兩種方法了解了尋找m 個奇數子數組的數量的方法-

• 產生每個子數組並檢查其中是否有m 個奇數，並遞增找到的每個子數組的計數。這段程式碼的時間複雜度是O(n2)。

• 高效的方法，遍歷數組的每個元素並創建一個前綴數組，然後用前綴數組的幫助。這段程式碼的時間複雜度是O(n)。

希望本文對您理解問題和解決方案有所幫助。

以上是使用C++編程，找出具有m個奇數的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！