মনে করুন, একটি পূর্ণসংখ্যা অ্যারে আছে। আমাদের সকল সম্ভাব্য জোড়ার মধ্যে k-তম ক্ষুদ্রতম দূরত্ব বের করতে হবে। একটি জোড়া (A, B)-এর দূরত্ব হচ্ছে |A - B|।
যেমন, ইনপুট [1,3,8] হলে, সকল জোড়া হলো [1,3], [3,8], [1,8]। k = 2 হলে, দ্বিতীয় ক্ষুদ্রতম দূরত্ব হলো ৫ (8 - 3)।
সমাধানের ধাপসমূহ
- n := nums.size(), x := 0
- সর্বোচ্চ উপাদান বের করুন (x)
- x+1 আকারের cnt অ্যারে সংজ্ঞায়িত করুন
- সকল জোড়া (i, j) এর জন্য cnt[|nums[j] - nums[i]|]++
- i := 0 থেকে x পর্যন্ত
- যদি cnt[i] >= k হয়, i রিটার্ন করুন
- k := k - cnt[i]
- x রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { int n = nums.size(); int x = 0; for(int i = 0; i < n; i++)x = max(x, nums[i]); vector <int> cnt(x + 1); for(int i = 0 ; i < n; i++){ for(int j = i + 1; j < n; j++){ cnt[abs(nums[j] - nums[i])]++; } } for(int i = 0; i <= x; i++){ if(cnt[i] >= k)return i; k -= cnt[i]; } return x; } }; main(){ Solution ob; vector<int> v = {1,3,8}; cout << (ob.smallestDistancePair(v, 2)); }
ইনপুট
{1,3,8}
আউটপুট
5
