資料結構
網路
關係資料庫管理系統 (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 次瀏覽
