資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中統計具有相同偶數和奇數元素的子陣列
給定一個正整數陣列。目標是在陣列中找到數字的子陣列，使得每個子陣列都具有相同數量的偶數和奇數元素。如果陣列是 { 1,2,3,4 }，則子陣列將是 {1,2}，{2,3}，{3,4}，{1,2,3,4}。此類子陣列的數量為 4。
讓我們透過例子來理解
輸入 − arr[] = {1,3,5,7,8,3,2 };
輸出 − 具有相同偶數和奇數元素的子陣列數量為 − 4
解釋 − 子陣列將是 − { 7,8 }，{8,3} {3,2}，{7,8,3,2}
輸入 − arr[] = {2,4,6 };
輸出 − 具有相同偶數和奇數元素的子陣列數量為 − 0
解釋 − 所有元素都是偶數。
下面程式中使用的演算法如下
在這種方法中，我們將使用一個變數temp作為陣列元素之間的差值（最初為0），如果arr[i]是奇數則將其加1，如果arr[i]是偶數則將其減1。當temp的值重複時，則必須存在一個子陣列，其在這些索引之間具有相同數量的偶數和奇數。temp可以是正數也可以是負數。取兩個雜湊陣列arr_1[size+1]用於正差值的頻率，arr_2[size+1]用於負差值的頻率。
對於每個差值temp<0，將arr_1[-temp]中的頻率新增到計數中。[-(-temp)]給出一個正索引。
對於每個差值temp>0，將arr_2[temp]中的頻率新增到計數中。由於相同差值的所有出現都將是子陣列的一部分。將這些頻率更新為1。
Arr[] = { 1,3,5,7,8,3,2 }從0開始的Temp值 −
1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4.子陣列是 − { 7,8 }，{8,3} {3,2}，{7,8,3,2}
將初始陣列作為arr[]。
函式Sub_even_odd(int arr[], int size)接受陣列及其長度並返回具有相同偶數和奇數元素的子陣列的數量。
將初始計數設定為0，並將變數temp設定為一個變數，當遇到奇數值時遞增，當遇到偶數值時遞減。
取兩個陣列arr_1[]和arr_2[]來儲存temp的頻率。arr_1[]用於temp的正值，如果整個陣列都是偶數，則最多可以達到size+1。
arr_2[]用於temp的負值，如果整個陣列都是偶數，則最多可以達到size+1。
使用for迴圈遍歷arr[]。
如果arr[i] & 1==1，這意味著arr[i]是奇數。遞增temp。否則遞減temp。
如果temp<0，則將arr_2[]中的相應頻率新增到計數中。將該頻率加1。
如果temp>0，則將arr_1[]中的相應頻率新增到計數中。將該頻率加1。
最後，我們計算了arr[]中具有相同數量的偶數和奇數元素的子陣列的數量
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++){
if(arr[i] & 1 == 1)
{ temp++; }
else
{ temp--; }
if (temp < 0){
count += arr_2[-temp];
arr_2[-temp]++;
}
else{
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main(){
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of subarrays with same even and odd elements are: 4
380 次瀏覽
