Chúng ta được cung cấp một mảng arr [] chứa các phần tử nguyên. Mục đích là tìm số lượng các cặp có thể được tạo thành bởi các phần tử của mảng con của arr [] sao cho mỗi mảng con chỉ có các phần tử riêng biệt. Nếu mảng là [1,2,2,3,3] thì các mảng con chỉ có các phần tử riêng biệt sẽ là [1,2] và [2,3]. Và các cặp sẽ là (1,2) và (2,3) do đó số lượng các cặp là 2.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,2,5,3}
Đầu ra - Số lượng các cặp được tạo thành bởi các mảng con phần tử riêng biệt là - 6
Giải thích - Các mảng con với các phần tử riêng biệt là:[1,2,5, 3], các cặp có thể có (1,2), (1,3), (1,5), (2,5), (2,3), (5,3)
Tổng số 6 cặp.
Đầu vào - arr [] ={1,2,1,2,3}
Đầu ra - Số lượng các cặp được tạo thành bởi các mảng con phần tử riêng biệt là - 5
Giải thích - Các mảng con có các phần tử riêng biệt là -
[1,2] - pairs: (1,2) [2,1] - pairs: (2,1) [1,2,3] - pairs : (1,2), (2,3), (1,3) Total pairs : 5
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Lấy một mảng số nguyên làm đầu vào.
-
Hàm diff_pairs (int arr [], int size) nhận mảng và trả về các cặp Đếm được tạo thành bởi các mảng con phần tử riêng biệt.
-
Lấy số lượng ban đầu là 0. Lấy các biến start =end =0.
-
Kiểm tra vectơ (kích thước, sai) để đánh dấu các phần tử trong cửa sổ.
-
Vòng lặp bắt đầu WHILE cho đến khi bắt đầu nhỏ hơn kích thước
-
Bên trong vòng lặp, bắt đầu một vòng lặp khác WHILE cho đến khi bắt đầu nhỏ hơn kích thước VÀ kiểm tra [arr [star]] =0, sau đó đặt số lượng là bắt đầu - kết thúc và đặt kiểm tra [arr [start]] là đúng và cũng tăng số bắt đầu bằng 1.
-
Bắt đầu Vòng lặp WHILE cho đến khi kết thúc ít hơn bắt đầu VÀ bắt đầu không bằng kích thước VÀ kiểm tra [arr [start]] =true sau đó đặt kiểm tra [arr [end]] =false và cũng tăng kết thúc bằng 1.
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
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 pairs formed by distinct element sub-arrays are: 17