C++ 选择距离最远的两个点之间距离小于等于L的三个点的方法

问题陈述要求我们确定选择三个点的方式，其中最远的两个点之间的距离小于或等于L，一个正整数将作为输入给出。

在问题中，我们将得到一个在x轴上的不同点的数组和一个大于0的整数L。任务是找到距离最远的两个点之间距离小于或等于整数L的三个点的集合的数量。

注意：给出的点集可以按照数组中给定的任意顺序排列。

以下给出的示例可以更好地理解这个问题。

输入

a[] = {5, 6, 7, 8}
L=3

输出

解释：从给定数组中距离最远的三个点的集合，距离小于或等于三，如下：

{5, 6, 7}，{5, 6, 8}，{5, 7, 8}和{6, 7, 8}。

从未出现在一个集合中距离最远的点相隔超过三倍的情况。

由于点集可以以任何顺序排列，所以{5,6,7}和{5,7,6}被认为是相似的三个点集。

输入

a[] = {3, 5, 6, 9}
L=3

输出

说明：由于三元组的最远两点之间的距离最多只能为3，只有一个可能的三元组，即{3, 5, 6}。

我们可以用不同的方法解决上述问题。让我们从简单的方法到高效的解决方案来看如何解决这个问题。

方法1

这将是解决问题的基本策略。该方法的目标是检查在提供的数组中可能存在的每个三元组，并确定其最远点之间的距离是否小于或等于指定的L值。如果三元组的最远点之间的距离小于或等于L，则计数三元组，否则继续寻找其他三元组。这将为我们提供选择三个点的每个选项，其中最远点的距离小于或等于L。

按照以下步骤，我们可以在代码中实现这个方法：

对给定数组进行排序，以便在给定数组中迭代时，我们可以检查每个可能的三元组，如a[i]<a[i+1]<a[i+2]。
声明一个名为count的变量，用于计算最远点小于或等于L的可能三元组的数量。
使用三个嵌套循环遍历整个数组，对每个可能的三元组进行遍历，第一个循环从x=0开始，第二个循环从y=x+1开始，第三个循环从z=y+1开始。
如果我们找到任何满足a[z]-a[x]<=L的三元组，我们将计数增加1，并继续遍历数组以寻找下一个可能的三元组。
遍历整个数组从i=0到i<array size-2，以检查所有可能的三元组，我们可以找到每种选择三个点的方式，其中最远的点<=L。

例子

//C++ code to find number of ways of choosing triplet

#include <bits/stdc++.h>

using namespace std;

//function to count the number of ways of choosing three points
int triplets(int a[], int N, int L){

   int count =0; //to count the total number of ways

   sort(a,a+N); //sorting the array using in-buit sort() function

   //iterating in the nested loops to check every triplet
   for(int x=0;x<N-2;x++){
      for(int y=x+1;y<N-1;y++){
         for(int z=y+1;z<N;z++){
            int furthest = a[z] - a[x];
            if(furthest<=L){ //if distance between the furthest points <=L
               count += 1; //increasing count by 1
            }
         }
      }
   }

   return count;  //return the possible number of ways satisfying the condition
}

int main()
{
   int a[] = {10, 2, 3, 7, 13, 9};
   int L=5;

   int N= sizeof(a)/sizeof(a[0]); //to calculate size of array

   cout<<"Total triplets possible : "<<triplets(a, N, L)<<endl;

   return 0;
}

输出

Total triplets possible : 3

时间复杂度：O(N^3)，其中N是给定数组的大小。

空间复杂度：O(1)，因为我们没有使用任何额外的空间。

方法2（高效方法）

上述朴素方法的高效解法是使用二分查找。我们将简单地在数组中从i=0到i<数组大小的范围内进行迭代。对于数组中的每个元素，我们将找到大于a[i]并且小于等于a[i]+L的点的数量。为了找到所有最远点之间的距离小于等于L的所有可能三元组，我们可以使用组合。
$^nC_{r}=\frac{n!}{(n-r)!r!}其中n是大于a[i]并且小于等于a[i]+L的点的数量，r是2，因为我们希望选择两个点来构成可能的三元组。$
因此，替换n和r的值，我们可以写成

三元组的数量 = 点的数量 * (点的数量 – 1)/2

使用这种方法，我们可以找到满足条件的每个点在数组中的可能三元组。

按照以下步骤在C++中实现此方法：

我们将创建一个函数来计算可能三元组的数量。
然后，对给定的数组进行排序以使用C++中的二分查找，使用sort()函数进行排序。
遍历整个数组，从i=0到i<数组的大小-2，计算每个元素的可能三元组。
对于每个元素a[i]，使用C++中的upper_bound函数找到第一个大于a[i]+L的元素的索引，它返回指向范围内大于传入值的指针。
为了找到大于a[i]并且小于等于L的点的数量，将大于a[i]+L的点的索引与i+1相减。
如果大于a[i]并且小于等于L的点的数量大于或等于2，则可以使用上述推导出的公式计算最远点小于等于L的可能三元组的数量，即点的数量 * (点的数量 – 1)/2。
计算给定数组中的每个元素，其中最远点之间的距离小于等于L的所有可能三元组。

例子

//C++ code to calculate number of possible ways to choose triplet using binary search
#include<bits/stdc++.h>

using namespace std;

//function to print the total triplets possible where distance
//between the furthest points <=L
int triplets(int a[], int N, int L)
{
   sort(a, a + N); //sort the array using sort() function

   int count = 0; //to count the number of ways possible


   for (int i = 0; i <= N-2; i++) {
       //using upper bound function to find the index greater than a[i]+L
     int index = upper_bound(a, a + N,a[i] + L) - a; 

      int x = index - (i + 1); //number of points

      if (x >= 2) {

         count += (x * (x - 1) / 2); 
      }
   }
   //return the total ways
   return count;
}

int main()
{
   int a[] = {4,7,3,9,8,10};
   int L = 6;

   int N = sizeof(a) / sizeof(a[0]); //to calculate the size of the array

   cout<<"Total triplets possible : "<<triplets(a, N, L)<<endl; //calling the function

   return 0;
}