ปัญหา
ได้รับอาร์เรย์ A มีบางตัวซ้ำ ต้องคืนองค์ประกอบที่ปรากฏมากกว่า 25% ของขนาดอาร์เรย์ เช่น A = [1,2,4,4,4,4,5,5,6,6,7,7] → 4 ปรากฏ 4 ครั้ง > 25% ของ 12
วิธีแก้
- อ่านองค์ประกอบและนับความถี่ (Frequency)
- ถ้าความถี่ > 25% ของขนาดอาร์เรย์ คืนค่าตัวนั้น
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
int n = arr.size();
int req = n / 4;
unordered_map<int, int> m;
int ans = -1;
for (int i = 0; i < n; i++) {
m[arr[i]]++;
if (m[arr[i]] > req) ans = arr[i];
}
return ans;
}
};
int main() {
Solution ob;
vector<int> c = {1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7};
cout << ob.findSpecialInteger(c);
}
อินพุต
[1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7]
เอาต์พุต
4
คำอธิบาย
ใช้ unordered_map นับความถี่ ขนาดอาร์เรย์ 12 → 25% = 3 ตัวที่ปรากฏ > 3 ครั้งคือคำตอบ (4 ปรากฏ 4 ครั้ง)
เนื่องจากอาร์เรย์เรียงลำดับแล้ว สามารถแก้ได้ O(1) Space โดยเช็ค arr[i] == arr[i + n/4] แต่โค้ดนี้ใช้ Hash Map ทั่วไป
