একটি সোর্টেড পূর্ণসংখ্যা অ্যারে এবং একটি মান num দেওয়া আছে। num-টি কতবার আসেছে তা দ্রুত বের করুন।
দুইটি পদ্ধতি
১. নেইভ পদ্ধতি (O(n))
লিনিয়ার স্ক্যান করে কাউন্ট করুন।
২. দক্ষ পদ্ধতি (O(log n)) - বাইনারি সার্চ
lower_bound: প্রথম অবস্থান যেখানেnumআছে বা থাকতে পারে।upper_bound: শেষ অবস্থানের পরের অবস্থান যেখানেnumআছে।- ফ্রিকোয়েন্সি =
upper_bound - lower_bound।
উদাহরণ
ইনপুট: [1,1,1,2,3,4], num=1
আউটপুট: 3
C++ বাস্তবায়ন (দক্ষ)
#include <bits/stdc++.h>
using namespace std;
int frequency_count(int arr[], int num, int size) {
int* first = lower_bound(arr, arr + size, num);
if (first == arr + size || *first != num)
return 0;
int* last = upper_bound(first, arr + size, num);
return last - first;
}
int main() {
int arr[] = {1, 1, 1, 2, 3, 4};
int num = 1;
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Frequency: " << frequency_count(arr, num, size);
return 0;
}
STL ফাংশন রেফারেন্স
lower_bound(first, last, val): প্রথমvalবা তার চেয়ে বড় এলিমেন্টের ইটেরেটর।upper_bound(first, last, val): প্রথমvalচেয়ে বড় এলিমেন্টের ইটেরেটর।- দউনোই O(log n) সময় নেয়।
