Chúng ta được cung cấp một mảng arr [] chứa các số nguyên. Mục đích là để đếm tất cả các mảng con của arr [] sao cho số phần tử riêng biệt trong mỗi mảng bằng với số phần tử riêng biệt trong mảng ban đầu. Nếu mảng ban đầu là [1,1,2,3] thì các mảng con sẽ là [1,2,3] và [1,1,2,3].
Tổng các phần tử khác biệt trong mảng ban đầu là 3. Tổng các phần tử khác biệt trong cả hai mảng con cũng là 3
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={1,2,1,2,3,4,2};
Đầu ra - Số mảng con có tổng số phần tử khác biệt giống với mảng ban đầu là - 6
Giải thích - Các phần tử phân biệt trong arr [] là 4 (1,2,3,4). Các mảng con có cùng số phần tử riêng biệt là:(đếm phân biệt từ trái sang phải)
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2 ]
Đầu vào - arr [] ={8,7,5,6,10};
Đầu ra - Số mảng con có tổng số phần tử khác biệt giống với mảng ban đầu là - 1
Giải thích - Các phần tử riêng biệt trong arr [] là 5 (5,6,7,8,10). Các mảng con có cùng số phần tử phân biệt là:(đếm phân biệt từ trái sang phải) [8,7,6,5,10]. 1 chỉ
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 [] gồm các số nguyên và tính kích thước của một mảng.
-
Hàm sub_ele_diff_one (int arr [], int size) nhận mảng và trả về số lượng các mảng con với các phần tử liên tiếp khác nhau bằng 1.
-
Lấy số lượng biến tạm thời và các biến bên phải và bên trái.
-
Lấy một biến kiểu unsrdered_map để tạo các cặp ngẫu nhiên.
-
Bắt đầu vòng lặp FOR từ 0 cho đến hết kích thước của một mảng và bên trong nó đặt giá trị của arr [i] bên trong bản đồ chưa có thứ tự.
-
Bây giờ, hãy tính toán kích thước của một bản đồ không có thứ tự và xóa bản đồ không có thứ tự.
-
Bắt đầu vòng lặp FOR từ 0 cho đến hết kích thước của một mảng.
-
Bên trong vòng lặp, bắt đầu WHILE cho đến phải
-
Tăng trước giá trị của ô [arr [right]]
-
Bây giờ, hãy kiểm tra xem um [arr [right]] =1 rồi tăng trước giá trị của trái lên 1.
-
Bên ngoài WHILE, tăng trước giá trị của quyền lên 1.
-
Kiểm tra NẾU left =kích thước của một bản đồ không có thứ tự, sau đó đặt số lượng thành đếm + kích thước - phải + 1
-
Giảm um [arr [i]] 1
-
Kiểm tra IF um [arr [i]] =0 rồi giảm bên trái 1
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i){
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for(int i = 0; i < size; ++i){
while (right < size && left < um_size){
++um[arr[right]];
if (um[arr[right]] == 1){
++left;
}
++right;
}
if (left == um_size){
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0){
--left;
}
}
return count;
}
int main(){
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(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 subarrays having total distinct elements same as original array are: 1