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