Chúng ta được cung cấp một mảng arr [] các số nguyên. Ngoài ra, hai số A và B. Mục đích là đếm tất cả các dãy con của arr [] sao cho số lần xuất hiện của A và B là bằng nhau. Nếu mảng là [1,2,3] và A là 1 và B là 2. Các mảng con sẽ là [3], [1,2], [1,2,3].
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={2, 2, 1, 1, 1, 5}; A =1, B =5
Đầu ra - Đếm các mảng con có số không bằng nhau. số lần xuất hiện của hai phần tử đã cho là - 4
Giải thích - Các tham số con sẽ là - [2], [2], [2,2], [1,5]. Ba đầu tiên có 0 lần xuất hiện là 1 và 5, lần cuối cùng có 1 lần xuất hiện của cả hai.
Đầu vào - arr [] ={5,3,7,5,3}; A =1, B =2
Đầu ra - Đếm các mảng con có số không bằng nhau. số lần xuất hiện của hai phần tử đã cho là - 15
Giải thích - Các tham số con sẽ là - (có 0 lần xuất hiện là 1 và 2)
[5], [3], [7], [5], [3] - 5 [5,3], [3,7], [7,5], [5,3] - 4 [5,3,7], [3,7,5], [7,5,3] - 3 [5,3,7,5], [3,7,5,3] - 2 [5,3,5,7,5] - 1
Tổng số 15 mảng con không có sự xuất hiện (0 lần xuất hiện) của cả 1 và 2.
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng hai vòng lặp for để tạo ra tất cả các mảng con có thể. Từ i =0 đến i <=size-1 và j =i đến j <=size-1. Các mảng con được hình thành sẽ nằm giữa arr [i] đến arr [j]. Đếm tần số của A và B trong mỗi mảng con. Nếu bằng nhau thì hãy tăng số lượng.
-
Lấy một mảng [] số.
-
Hàm sub_EqualOcchood (int arr [], int size, int A, int B) nhận mảng và trả về số lượng các mảng con có số bằng nhau. của A và B.
-
Lấy số lượng ban đầu là 0.
-
Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng hai vòng lặp for từ i =0 đến i <=size-1 và j =0 đến j <=size-1.
-
Lấy hai biến total_A, total_B bằng 0 cho số của A và B trong mảng con arr [i] đến arr [j].
-
So sánh arr [j] với A và B. Nếu arr [j] là A hoặc B thì số đếm tương ứng tăng dần (tổng_A hoặc tổng_bố_B).
-
Nếu total_A ==total_B. Số lượng tăng dần. (mảng con có cùng số phần tử A và B).
-
Ở cuối cả hai vòng, kết quả trả về là số lượng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int sub_EqualOccurrence(int arr[], int size, int A, int B){
int count = 0;
for (int i = 0; i <= size - 1; i++){
int total_A = 0;
int total_B = 0;
for (int j = i; j <= size - 1; j++){
if (arr[j] == A){
total_A++;
}
else if (arr[j] == B){
total_B++;
}
if(total_A == total_B){
count++;
}
}
}
return count;
}
// Driver code
int main(){
int arr[] = { 2, 3, 1, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
int A = 1, B = 5;
cout<<"Count of subarrays with equal number of occurrences of two given elements are: "<<sub_EqualOccurrence(arr, size, A, B);
return (0);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of subarrays with equal number of occurrences of two given elements are: 5