使用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中文网其他相关文章！