কাউন্ট অফ স্মলার নাম্বার্স আফ্টার সেলফ
একটি অ্যারে nums দেওয়া আছে। প্রতিটি সূচক i-র জন্য, i-র ডানে (অর্থাৎ j > i) কতগুলো উপাদান nums[i]-র চেয়ে ছোট তা গণনা করতে হবে।
উদাহরণ: [5,2,7,1] → [2,1,1,0]
সমাধানের পদ্ধতি (বাইনারি ইনডেক্সড ট্রি / BIT / ফেনউইক ট্রি)
- কোঅর্ডিনেট কমপ্রেশন: মানগুলো ১ থেকে
maxValরেঞ্জে নিয়ে আসুন BIT(ফেনউইক ট্রি) ব্যবহার করে প্রিফিক্স সম কوئরি করুন- ডান থেকে বামে ট্রাভার্স করুন:
query(nums[i]-1)দিয়ে ছোট মানগুলোর কাউন্ট পানupdate(nums[i], 1)দিয়ে বর্তমান মান যোগ করুন
C++ কোড উদাহরণ
0) {
ans += bit[index];
index -= index & (-index);
}
return ans;
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
if(!n) return res;
int minn = nums[0], maxx = 0;
for(int i = 1; i < n; i++) minn = min(nums[i], minn);
for(int i = 0; i < n; i++) {
nums[i] = nums[i] - minn + 1;
maxx = max(nums[i], maxx);
}
vector<int> bit(maxx + 1);
for(int i = n-1; i >= 0; i--) {
int num = nums[i] - 1;
int x = query(num, bit);
res[i] = x;
update(num + 1, bit, maxx);
}
return res;
}
};
int main() {
Solution ob;
vector<int> v = {5,2,7,1};
print_vector(ob.countSmaller(v));
return 0;
}
ইনপুট
[5,2,7,1]
আউটপুট
[2, 1, 1, 0, ]
