AP 是等差數列，其中兩個連續元素之間的差異總是相同。我們將使用三種方法列印形成 AP 的排序數組中的所有三元組：樸素方法、二分搜尋方法和兩個指標方法。
在這個問題中，我們得到一個排序數組，這意味著所有元素都是遞增的形式。我們必須找到數組中的三個元素並形成一個 AP。例如 -
給定數組：1 5 2 4 3
從給定的陣列中，我們有兩個三元組：1 2 3 和 5 4 3，因為相鄰元素之間的差異相等。另外，正如所寫，我們只需找到三元組，這樣我們就不會找到任何更長的序列。
讓我們轉向尋找三元組的方法 -
在這種方法中，我們只是使用循環在數組上移動，並且對於每次迭代，我們將為與當前索引相比更大的數字運行另一個數組。然後我們將在第一個巢狀數組中再次實作一個巢狀數組，以尋找可以形成AP的元素。讓我們看看程式碼 -
// function to find all the triplets
function findAP(arr){
var n = arr.length
// traversing over the array
for(var i = 0; i< n;i++){
for(var j = i+1;j<n;j++){
for(var k = j+1; k < n; k++){
if(arr[j] - arr[i] == arr[k] - arr[j]) {
console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + arr[k]);
}
}
}
}
}
// defining the array and calling the function
arr = [1, 5, 2, 4, 3]
findAP(arr)
上述程式碼的時間複雜度為O()，其中N為陣列的大小。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
在前面的方法中，當我們有兩個元素時，我們可以找到第三個元素，因為我們有共同的差異，所以要找到第三個元素，而不是使用線性搜索，我們可以使用二分搜尋並降低時間複雜度上面的程式碼-
// function for binary search
var binarySearch = function (arr, x, start, end) {
if (start > end) return false;
var mid=Math.floor((start + end)/2);
if (arr[mid]===x) return true;
if(arr[mid] > x)
return binarySearch(arr, x, start, mid-1);
else
return binarySearch(arr, x, mid+1, end);
}
// function to find all the tripletes
function findAP(arr){
var n = arr.length
// traversing over the array
for(var i = 0; i< n;i++){
for(var j = i+1;j<n;j++){
// third element will be
var third = 2*arr[j]-arr[i];
if(binarySearch(arr,third,j+1,n)){
console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + third);
}
}
}
}
// defining the array and calling the function
arr = [1, 5, 2, 4, 3]
findAP(arr)
上述程式碼的時間複雜度為O()，其中N為陣列的大小。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
在這種方法中，我們將使用兩個指標並尋找與目前位置具有相同差異的元素。讓我們看看程式碼 -
// function to find all the triplets
function findAP(arr){
var n = arr.length
// traversing over the array
for(var i = 1; i< n;i++) {
var bptr = i-1
var fptr = i+1
while(bptr >= 0 && fptr < n) {
if(arr[i] - arr[bptr] == arr[fptr] - arr[i]){
console.log("Triplet is: " + arr[bptr] + " " + arr[i] + " " + arr[fptr]);
bptr--;
fptr++;
}
else if(arr[i] - arr[bptr] > arr[fptr] - arr[i]){
fptr++;
}
else{
bptr--;
}
}
}
}
// defining the array and calling the function
arr = [1, 4, 7, 10, 13, 16]
findAP(arr)
上述程式碼的時間複雜度為 O(N*N)，其中 N 是給定陣列的大小，上述方法的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。 p>
注意 - 前兩種方法對於任何類型的已排序或未排序的數組都是有效的，但最後一種方法僅適用於已排序的數組，如果數組未排序，我們可以對其進行排序一種方法，但這種方法仍然是所有其他方法中最好的。
在本教程中，我們實作了一個 JavaScript 程式來列印給定排序數組中形成 AP 的所有三元組。 Ap 是算術級數，其中兩個連續元素之間的差異始終相同。我們已經看到了三種方法：時間複雜度為 O(N*N*N) 的樸素方法、時間複雜度為 O(N*N*log(N)) 的二分查找方法以及雙指針方法。
以上是用於列印排序數組中形成 AP 的所有三元組的 JavaScript 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章！
