ในปัญหานี้ เราได้รับ N ช่วง งานของเราคือ จำนวนเต็มที่เกิดขึ้นสูงสุดในช่วง n ช่วง .
สำหรับค่าเริ่มต้นและสิ้นสุดของทุกช่วง เราต้องหาค่าที่เกิดขึ้นให้ได้มากที่สุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
ผลผลิต
2
แนวทางการแก้ปัญหา
วิธีง่ายๆในการแก้ปัญหาคือการใช้แฮช เราจะใช้ตารางแฮชเพื่อนับสมาชิกทั้งหมดและจำนวนสมาชิก เราจะสำรวจทุกช่วงและเก็บจำนวนไว้ในตารางแฮช จากนั้นเราจะหาจำนวนสูงสุด
อีกวิธีหนึ่งในการแก้ปัญหาในเวลาเชิงเส้นคือการใช้อาร์เรย์ช่วง ในอาร์เรย์นี้ เราจะอัปเดตดัชนีของค่าเริ่มต้นทั้งหมดของช่วงโดยการเพิ่ม 1 และค่าสิ้นสุดทั้งหมดของช่วงโดยลบ 1 ออกจากค่านั้น จะค้นหาผลรวมคำนำหน้าและค้นหาค่าผลรวมคำนำหน้าสูงสุด
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum occurred integer in the range is 3
