資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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 個位置開始的每個元素。如果當前元素為奇數，則增加奇數計數器，併為每個偶數增加偶數計數器。如果我們找到一個奇數，則交換偶數和奇數的值，因為向子陣列新增奇數將改變其奇偶校驗，最後將計數新增到結果中。此程式碼的複雜度為 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
以上程式碼的解釋
在此程式碼中，我們檢查每個元素的奇偶性，併為找到的每個偶數遞增偶數計數器，為每個奇數遞增奇數計數器。此外，如果找到奇數，我們正在交換奇偶計數器值；否則，它將改變子陣列的奇偶校驗。然後在每次迭代後將奇數計數器的值新增到結果變數中。
結論
在本文中，我們解釋瞭如何從暴力方法中找到奇數和的子陣列數量，該方法生成每個奇數和的子陣列並遞增計數。此程式碼的時間複雜度為 O(n2)。一種有效的方法是遍歷陣列的每個元素，併為找到的每個奇數/偶數遞增奇數/偶數計數器變數，並在找到奇數時交換計數器；此程式碼的時間複雜度為 O(n)。希望您發現本文有助於理解問題和解決方案。
372 次檢視
