在C ++中找到第K个最小的配对距离

假设我们有一个整数数组;我们必须找到所有对中的第k个最小距离。一对(A,B)的距离实际上是A和B之间的绝对差。因此,如果输入像[1,3,8],则所有可能的对都是[1,3],[3、8] ,[1,8],则当k = 2时,第二个最小距离是5(8-3)。

为了解决这个问题,我们将遵循以下步骤-

  • n:= nums的大小,x:= 0

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • x:= x和nums的最大值[i]

  • 定义大小为x + 1的数组cnt

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • 将cnt [| nums [j]-nums [i] |]增加1

    • 对于初始化j:= i + 1,当j <n时,更新(将j增加1),-

  • 对于初始化i:= 0,当i <= x时,更新(将i增加1),执行-

    • 还给我

    • 如果cnt [i]> = k,则-

    • 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

以上是 在C ++中找到第K个最小的配对距离 的全部内容, 来源链接: utcz.com/z/340870.html

回到顶部