ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে সংখ্যা রয়েছে, আমাদের প্রদত্ত অ্যারের সংখ্যাগুলির একটি অ্যারের উপসর্গের সর্বাধিক সম্ভাব্য দৈর্ঘ্য ফিরিয়ে দিতে হবে, যেমন এই উপসর্গ থেকে ঠিক একটি উপাদান মুছে ফেলা সম্ভব যাতে এটিতে উপস্থিত প্রতিটি সংখ্যা একই ফ্রিকোয়েন্সি আছে। একটি উপাদান অপসারণের পরে যদি কোনো অবশিষ্ট উপাদান না থাকে, তবুও এটি বিবেচনা করা হয় যে প্রতিটি উপস্থিত সংখ্যার একই ফ্রিকোয়েন্সি (0) রয়েছে।
সুতরাং, যদি ইনপুটটি [3,3,2,2,6,4,4,6] এর মত হয়, তাহলে আউটপুট হবে 7, তাই যদি আমরা সূচক 4 থেকে উপাদান 6 সরিয়ে ফেলি, তাহলে সাবয়ারে হবে [3, 3,2,2,4,4] যেখানে সমস্ত উপাদান দুইবার উপস্থিত হয়েছিল।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
maxf :=0, res :=0
-
মানচিত্র সংজ্ঞায়িত করুন cnt এবং freq
-
আরম্ভ করার জন্য i :=0, যখন i <সংখ্যার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
x :=সংখ্যা[i]
-
(cnt[x] 1 দ্বারা বৃদ্ধি করুন)
-
f :=cnt[x]
-
(1 দ্বারা ফ্রিকোয়েন্সি [f] বাড়ান)
-
ফ্রিকোয়েন্সি [f - 1] 1
কমিয়ে দিন -
maxf :=maxf এবং f
এর সর্বোচ্চ -
যদি maxf * freq[maxf] i বা (maxf - 1) * (freq[maxf - 1] + 1) i এর মত হয় বা maxf 1 এর মত হয়, তাহলে −
-
res :=i + 1
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
int maxf = 0, res = 0;
map<int, int> cnt, freq;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
cnt[x]++;
int f = cnt[x];
freq[f]++;
freq[f - 1]--;
maxf = max(maxf, f);
if (maxf * freq[maxf] == i || (maxf - 1) * (freq[maxf - 1] + 1) == i || maxf == 1) {
res = i + 1;
}
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {3,3,2,2,6,4,4,6};
cout << (ob.maxEqualFreq(v));
} ইনপুট
{3,3,2,2,6,4,4,6} আউটপুট
7
