C++ এ K-তম সবচেয়ে ছোট জোড়া দূরত্ব খুঁজুন

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে; আমাদের সব জোড়ার মধ্যে kth ক্ষুদ্রতম দূরত্ব খুঁজে বের করতে হবে। একটি জোড়ার দূরত্ব (A, B) আসলে A এবং B এর মধ্যে পরম পার্থক্য। তাই যদি ইনপুটটি [1,3,8] এর মত হয়, তাহলে সম্ভাব্য সব জোড়া হল [1,3], [3, 8] , [1, 8], তারপর যখন k =2, দ্বিতীয় ক্ষুদ্রতম দূরত্ব হল 5 (8 - 3)।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সংখ্যার আকার, x :=0
• আরম্ভ করার জন্য i :=0, যখন i করুন
• x :=সর্বাধিক x এবং সংখ্যা[i]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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