Trong bài toán này, chúng ta có N dãy. Nhiệm vụ của chúng tôi là số nguyên tối đa đã xảy ra trong n phạm vi .
Đối với giá trị bắt đầu và kết thúc của tất cả các phạm vi. Chúng ta cần tìm giá trị xuất hiện nhiều nhất.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
Đầu ra
2
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là bằng cách sử dụng băm, chúng ta sẽ sử dụng một bảng băm để đếm tất cả các thành viên và số lượng của chúng. Chúng tôi sẽ duyệt qua tất cả các phạm vi và lưu trữ số lượng trong bảng băm, sau đó chúng tôi sẽ tìm ra số lượng tối đa.
Một cách tiếp cận khác để giải quyết vấn đề trong thời gian tuyến tính là sử dụng một mảng phạm vi. Trong mảng này, chúng tôi sẽ cập nhật chỉ số của tất cả các giá trị bắt đầu của dải ô bằng cách cộng 1 và tất cả các giá trị cuối của dải ô bằng cách trừ đi 1 từ nó. Sẽ tìm tổng tiền tố và tìm giá trị tổng tiền tố lớn nhất.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
int occurenceConut[MAX];
memset(occurenceConut, 0, sizeof occurenceConut);
int maxi = -1;
for (int i = 0; i < n; i++) {
occurenceConut[L[i]] += 1;
occurenceConut[R[i] + 1];
if(R[i]>maxi){
maxi=R[i];
}
}
int prefSum = occurenceConut[0],maxEleIndex;
for (int i = 1; i < maxi+1; i++) {
occurenceConut[i] += occurenceConut[i - 1];
if (prefSum < occurenceConut[i]) {
prefSum = occurenceConut[i];
maxEleIndex = i;
}
}
return maxEleIndex;
}
int main(){
int L[] = { 1, 2, 3 };
int R[] = { 3, 6, 4 };
int n = sizeof(L) / sizeof(L[0]);
cout<<"The maximum occurred integer in the range is "<<findMaxOccrEle(L, R, n);
return 0;
} Đầu ra
The maximum occurred integer in the range is 3