首页 > 后端开发 > C++ > 使用C++编写代码,找到具有奇数和的子数组的数量

使用C++编写代码,找到具有奇数和的子数组的数量

王林
发布: 2023-09-21 08:45:03
转载
1438 人浏览过

使用C++编写代码,找到具有奇数和的子数组的数量

子数组是数组的连续部分。例如,我们考虑一个数组 [5, 6, 7, 8],那么有十个非空子数组,如 (5), (6), (7), (8), (5, 6), (6 ,7)、(7,8)、(5,6,7)、(6,7,8) 和 (5,6,7,8)。

在本指南中,我们将解释在 C++ 中查找所有可能的信息来查找具有奇数和的子数组的数量。为了找到奇数和的子数组的数量,我们可以使用不同的方法,所以这里是一个简单的例子 -

Input : array = {9,8,7,6,5}
Output : 9

Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35
登录后复制

暴力方法

通过这种方法,我们可以简单地检查所有子数组中元素的总和是偶数还是奇数,如果是偶数,我们将拒绝该子数组并计算总和为奇数的子数组,这不是一种有效的方法,因为此代码的复杂度为 O(n2)。

示例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n=5, temp = 0;
    int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
    int cnt = 0; // counter variable.
    for(int i = 0; i < n; i++){
        temp = 0; // refreshing our temp sum.
        for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
            temp = temp + a[j];
            if( temp % 2 == 1 )
                cnt++;
        }
    }
    cout << "Number of subarrays with odd sum : " << cnt << "\n";
    return 0;
}
登录后复制

输出

Number of subarrays with odd sum : 9
登录后复制
登录后复制

上述代码说明

此代码中使用了嵌套循环,其中外层循环用于递增 I 的值,I 指向数组从头开始的每个值;内循环用于查找从位置 " i " 开始的具有奇数和的子数组。

高效方法

在这种方法中,我们正在处理每个从数组中第 0 个位置开始的元素。如果当前元素是奇数,则为每个偶数增加一个奇数计数器并增加一个偶数计数器。如果我们找到一个奇数,则交换 Even 和 odd 的值,因为向子数组添加奇数会改变其奇偶校验,最后向结果添加一个计数。这段代码的复杂度是 O(n),因为我们正在处理每个元素。

示例

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int odd = 0, even = 0,  result = 0,n=5,i,temp;
    int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
     // for loop for processing every element of array
    for ( i = 0 ; i < n ; i ++ )  {
        if ( arr[ i ] % 2 == 0 ) {
            even++;
        } else {
          // swapping even odd values
            temp = even;
            even = odd;
            odd = temp + 1;
        }
        result += odd;
    }
    cout << "Number of subarrays with odd sum : " << result;
}
登录后复制

输出

Number of subarrays with odd sum : 9
登录后复制
登录后复制

上述代码的解释

在这段代码中,我们检查每个元素的偶数/奇数,并为偶数增加偶数计数器,为奇数增加奇数计数器。此外,如果找到奇数,我们将交换奇偶计数器值;否则,它将改变子数组的奇偶校验。然后在每次迭代后将奇数计数器的值添加到结果变量中。

结论

在本文中,我们解释了如何从 Brute 中查找总和为奇数的子数组的数量强制方法,生成每个子数组的总和为奇数并递增计数。这段代码的时间复杂度是O(n2)。一种有效的方法是遍历数组的每个元素,并用找到的每个奇数/偶数增加奇数/偶数计数器变量,如果找到奇数则交换计数器;这段代码的时间复杂度是O(n)。希望您发现本文有助于理解问题和解决方案。

以上是使用C++编写代码,找到具有奇数和的子数组的数量的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板