数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学选择三个点的方法，使其最远两点之间的距离小于等于 L
题目要求我们计算选择三个点的方案数，使得这三个点中最远两点之间的距离小于等于 L，其中 L 是一个给定的正整数。
题目中给定一个位于 x 轴上的不同点的数组和一个大于 0 的整数 L。任务是找到三点集合的个数，其中最远两点之间的距离小于等于整数 L。
注意：点集的顺序可以与数组中给定的顺序不同。
我们可以通过以下示例更好地理解这个问题。
输入
a[] = {5, 6, 7, 8}
L=3
输出
4
解释：从给定数组中，最远两点距离小于等于 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
输出
1
解释：由于三元组中最远两点之间的距离最多只能为 3。只有一个可能的三元组，即 {3, 5, 6}。
我们可以使用不同的方法在 C++ 中解决上述问题。让我们从朴素方法到高效解决方案来研究解决问题的方法。
方法一
这是解决问题的基本策略。该方法的目标是检查给定数组中可能存在的每个三元组，并确定最远两点之间的距离是否小于等于 L 的指定值。如果最远两点之间的距离小于等于 L，则计数三元组；否则，我们将寻找更多三元组。这将为我们提供所有选择三个点的方案，使最远两点之间的距离小于等于 L。
按照以下步骤，我们可以将此方法实现到我们的代码中
对给定数组进行排序，以便在给定数组中迭代时，我们可以检查每个可能的三元组，使得 a[i]<a[i+1]<a[i+2]。
声明一个名为 count=0 的变量来计算可能的三元组数，其最远两点距离小于等于 L。
使用三个嵌套循环遍历整个数组，用于从第一循环中的 x=0、第二循环中的 y=x+1 和第三循环中的 z=y+1 开始的每个三元组。
如果我们找到任何满足 a[z]-a[x]<=L 的三元组，我们将计数加 1 并继续遍历数组以寻找下一个可能的三元组。
遍历整个数组，从 i=0 到 i<数组大小-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)，因为我们没有使用任何额外的空间。
方法二（高效方法）
上述朴素方法的高效解决方案可以使用二分查找。我们将简单地从 i=0 迭代到 i<数组大小的数组。对于数组中存在的每个元素，我们将找到大于 a[i] 并小于等于 a[i]+L 的点数。为了找到所有可能的三元组 a[i]，其中最远两点之间的距离小于等于 L，我们可以使用组合。
$\mathrm{^n{C_{r}}=\frac{n!}{(n-r)!r!}}$ 其中 n 将是大于 a[i] 并小于等于 a[i]+L 的点数，r 将是 2，因为我们想要选择两个点来构成一个可能的三元组。
因此，替换 n 和 r 的值，我们可以写成
三元组数 = 点数 * (点数 - 1)/2
使用这种方法，我们可以找到满足数组中每个元素（即 a[i]）条件的每个可能的三元组。
按照以下步骤在 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] 并 <=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;
}
输出
Total triplets possible: 16
时间复杂度：O(NlogN)，其中 N 是数组的大小。
空间复杂度：O(1)，因为没有使用额外的空间。
结论
阅读完这篇文章后，我希望你对这个问题的所有概念都已清楚。
146 次查看
