สมมติว่าเรามีอาร์เรย์ A มีองค์ประกอบน้อย องค์ประกอบบางอย่างเป็นเรื่องปกติ เราต้องส่งคืนองค์ประกอบที่ปรากฏมากกว่าช่องว่าง 25% ในอาร์เรย์ ดังนั้น ถ้า A =[1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7] นี่ 4 เกิดขึ้นสี่ครั้ง ซึ่งมากกว่า 25% ของ 12 (ขนาดของอาร์เรย์)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- อ่านองค์ประกอบและจัดเก็บความถี่ตามลำดับ
- หากความถี่มากกว่า 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;
}
};
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
