C++에서 K번째 최소 쌍 거리 찾기

정수 배열이 있다고 가정합니다. 모든 쌍 중에서 k번째로 가장 작은 거리를 찾아야 합니다. 쌍 (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 및 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