Jika anda pernah menggunakan C++, anda mesti tahu apa itu subarray dan betapa bergunanya ia. Seperti yang kita semua tahu bahawa dalam C++ kita boleh menyelesaikan pelbagai masalah matematik dengan mudah. Jadi, dalam artikel ini, kami akan menerangkan cara untuk mencari maklumat lengkap nombor ganjil M dengan bantuan subarray ini dalam C++.
Dalam masalah ini, kita perlu mencari beberapa subarray dan integer m yang terdiri daripada tatasusunan yang diberikan, di mana setiap subarray mengandungi tepat m nombor ganjil. Berikut ialah contoh mudah pendekatan ini -
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 }
Dalam pendekatan ini semua sub-tatasusunan yang mungkin dijana daripada tatasusunan yang diberikan, Dan semak sama ada setiap subarray mempunyai betul-betul m nombor ganjil. Ini ialah kaedah penjanaan dan carian mudah dengan kerumitan masa 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
#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 };
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]; }
Atas ialah kandungan terperinci Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!