資料結構
網路
關係型資料庫管理系統 (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 次檢視
