C++でK番目に小さいペア距離を見つける

整数配列があるとします。すべてのペアの中でk番目に小さい距離を見つける必要があります。ペア（A、B）の距離は、実際にはAとBの絶対差です。したがって、入力が[1,3,8]の場合、可能なすべてのペアは[1,3]、[3、8]です。 、[1、8]、k =2の場合、2番目に小さい距離は5（8-3）です。

これを解決するには、次の手順に従います-

• n：=numsのサイズ、x：=0
• iを初期化する場合：=0、i
• x：=xとnumsの最大値[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