Nếu bạn đã từng sử dụng C ++, bạn phải biết các subarrays là gì và chúng hữu ích như thế nào. Như chúng ta đã biết, trong C ++, chúng ta có thể giải quyết nhiều vấn đề toán học một cách dễ dàng. Vì vậy, trong bài viết này, chúng tôi sẽ giải thích thông tin đầy đủ về cách chúng tôi có thể tìm M số lẻ với sự trợ giúp của các mảng con này trong C ++.
Trong bài toán này, chúng ta cần tìm nhiều mảng con được tạo thành với mảng và số nguyên m đã cho trong đó mỗi mảng con chứa đúng m số lẻ. Đây là ví dụ đơn giản của cách tiếp cận này -
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 } Phương pháp tiếp cận đầu tiên
Theo cách tiếp cận này, tất cả các mảng con có thể được tạo ra từ một mảng nhất định và mỗi mảng con được kiểm tra xem có chính xác m số lẻ hay không. Đây là một phương pháp tạo và tìm đơn giản, và độ phức tạp về thời gian của phương pháp này là O (n 2 ).
Ví dụ
#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;
} Đầu ra
Number of subarrays with n numbers are: 6
Giải thích về Quy tắc trên
Trong đoạn mã này, chúng tôi đang sử dụng các vòng lặp lồng nhau để tìm các mảng con có m số lẻ và vòng lặp bên ngoài được sử dụng để tăng "i", sẽ được sử dụng để xử lý từng phần tử trong một mảng.
Vòng lặp bên trong được sử dụng để tìm mảng con và xử lý các phần tử cho đến khi bộ đếm lẻ đạt đến m, tăng số lượng bộ đếm kết quả cho mỗi mảng con được tìm thấy và cuối cùng in kết quả được lưu trữ trong biến đếm.
Phương pháp tiếp cận thứ hai
Một cách tiếp cận khác là tạo một mảng để lưu trữ số tiền tố có số lẻ "i", xử lý mọi phần tử và tăng số lượng số lẻ cho mỗi số lẻ được tìm thấy.
Khi số lượng các số lẻ vượt quá hoặc trở nên bằng m, hãy thêm số ở vị trí (lẻ - m) trong mảng tiền tố.
Khi số lẻ lớn hơn hoặc bằng m, chúng tôi tính số mảng con được hình thành cho đến khi chỉ số và số "lẻ - m" được thêm vào biến đếm. Kết quả được lưu trữ trong biến đếm sau khi mọi phần tử được xử lý.
Ví dụ
#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;
} Đầu ra
Number of subarrays with n numbers are: 6
Giải thích về Quy tắc trên
Khởi tạo mảng và biến có giá trị bắt đầu -
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 }; Trong phần này, chúng ta đang khởi tạo biến n với kích thước của mảng, m với một số số lẻ cần tìm, đếm với 0 để giữ số lượng các mảng con có thể có, lẻ với 0 và prefix_array có kích thước n + 1 với 0.
Hiểu vòng lặp
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];
} Trong vòng lặp này, chúng tôi đang triển khai các giá trị tại chỉ số lẻ trong prefix_array [], sau đó tăng dần các biến lẻ nếu tìm thấy một số lẻ. Chúng tôi nhận thấy số lượng mảng con có thể được hình thành cho đến khi chỉ mục khi một biến lẻ trở nên bằng hoặc lớn hơn m.
Cuối cùng, chúng tôi in một số mảng con với m số lẻ được lưu trữ trong các biến đếm và nhận được kết quả.
Kết luận
Trong bài viết này, chúng ta hiểu cách tiếp cận để tìm số lượng các mảng con có m số lẻ từ hai cách tiếp cận -
-
Tạo mọi mảng con và kiểm tra m số lẻ trong đó và tăng số lượng cho mỗi mảng con được tìm thấy. Độ phức tạp về thời gian của mã này là O (n2).
-
Cách tiếp cận hiệu quả, đó là đi qua từng phần tử của mảng và tạo mảng tiền tố, đồng thời tìm kết quả với sự trợ giúp của mảng tiền tố. Độ phức tạp về thời gian của mã này là O (n).
Hy vọng bạn thấy bài viết này hữu ích trong việc hiểu vấn đề và giải pháp.