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中文网其他相关文章！
