Trong bài này, chúng ta sẽ giải quyết vấn đề tìm số lượng các mảng con có phần tử cực đại và cực tiểu bằng nhau bằng C ++. Đây là ví dụ cho vấn đề -
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same. Phương pháp tiếp cận để tìm giải pháp
Nhìn vào các ví dụ, chúng ta có thể nói số lượng mảng con tối thiểu có thể được hình thành với các phần tử tối thiểu và tối đa giống nhau bằng kích thước của mảng. Số lượng mảng con có thể nhiều hơn nếu có các số liên tiếp giống nhau.
Vì vậy, chúng ta có thể áp dụng phương pháp đi qua mọi phần tử và kiểm tra xem các số liên tiếp của nó có giống nhau hay không và đếm số gia tăng nếu các số liên tiếp giống nhau và ngắt vòng lặp bên trong nếu tìm thấy một số khác.
Biến kết quả tăng biến kết quả mỗi khi vòng lặp bên trong kết thúc hoặc ngắt và cuối cùng hiển thị kết quả từ biến kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count =0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i]==a[j])
count++;
else
break;
}
result+=count;
count =0;
}
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} Đầu ra
Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n2).
Giải thích mã trên
Trong đoạn mã này, chúng tôi đang sử dụng biến n để lưu trữ kích thước của mảng, result =n, vì n tối thiểu mảng con có thể được hình thành và đếm để giữ cho số lượng các số giống nhau.
Vòng lặp ngoài được sử dụng để xử lý mọi phần tử trong một mảng. Vòng lặp bên trong được sử dụng để tìm bao nhiêu số liên tiếp giống nhau sau phần tử chỉ số và tăng biến kết quả với biến đếm mỗi khi vòng lặp bên trong kết thúc. Cuối cùng là hiển thị kết quả được lưu trữ trong biến kết quả.
Cách tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ xem xét từng phần tử và đối với mỗi phần tử, chúng tôi đang tìm kiếm xem có bao nhiêu số giống nhau liên tiếp. Đối với mỗi số giống nhau được tìm thấy, chúng tôi đang tăng biến đếm và khi các số khác nhau được tìm thấy thì với sự trợ giúp của số, chúng tôi sẽ tìm ra bao nhiêu mảng con có thể được hình thành bằng cách sử dụng công thức "n =n * (n + 1) / 2 " và tăng biến kết quả với câu trả lời của công thức này.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count =1,temp=a[0];
for (int i = 1; i < n; i++) {
if (temp==a[i]){
count++;
}
else{
temp=a[i];
result = result + (count*(count+1)/2);
count=1;
}
}
result = result + (count*(count+1)/2);
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} Đầu ra
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
Giải thích mã trên
Trong đoạn mã này, chúng tôi lưu trữ chỉ số 0 của mảng trong biến tạm thời và bắt đầu vòng lặp với chỉ số 1. Chúng tôi kiểm tra xem biến tạm thời có bằng với phần tử ở chỉ mục hiện tại hay không và tăng số đếm lên 1 cho cùng một số được tìm thấy. Nếu biến tạm thời không bằng phần tử chỉ số, thì chúng ta tìm các tổ hợp của các mảng con có thể được tạo ra từ việc đếm các số giống nhau và lưu trữ kết quả trong biến kết quả. Chúng tôi thay đổi giá trị tạm thời thành số đặt lại chỉ mục hiện tại thành 1. Cuối cùng, chúng tôi đang hiển thị câu trả lời được lưu trữ trong biến kết quả.
Kết luận
Trong bài này, chúng ta giải một bài toán để tìm Số lượng các mảng con có phần tử tối thiểu và tối đa giống nhau. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.