数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 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(n2)。
示例
#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，最后打印存储在 count 变量中的结果。
第二种方法
另一种方法是创建一个数组来存储具有“i”个奇数的前缀的数量，处理每个元素，并为找到的每个奇数增加奇数的数量。
当奇数计数超过或等于 m 时，在 prefix 数组中添加 (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 初始化 count 以计数可能的子数组，使用 0 初始化 odd，以及使用 0 初始化大小为 n+1 的 prefix_array。
理解循环
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)。
希望本文能帮助您理解问题和解决方案。
194 次浏览
