用给定的差值找到一对的 Php 程序
给定一个未排序的数组和一个数字 n，找出数组中是否有一对元素的差为 n。 示例:
Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)
Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair
最简单的方法是运行两个循环，外部循环挑选第一个元素(较小的元素)，内部循环寻找由外部循环加上 n 挑选的元素。这个方法的时间复杂度是 O(n^2). 我们可以使用排序和二分搜索法来提高时间复杂度到 O(nLogn)。第一步是按升序对数组进行排序。一旦数组被排序，从左到右遍历数组，对于每个元素 arr[i]，arr[I+1]中 arr[i] + n 的二分搜索法..n-1]。如果找到该元素，则返回该对。 第一步和第二步都采用 0(nLogn)。所以整体复杂度是 O(nLogn)。 上述算法的第二步可以改进为 O(n)。第一步保持不变。第二步的想法是取两个索引变量 I 和 j，分别初始化为 0 和 1。现在运行一个线性循环。如果 arr[j]–arr[i]小于 n，我们需要寻找更大的 arr[j]，所以增量为 j .如果 arr[j]–arr[I]大于 n，我们需要寻找更大的 arr[I]，所以增量为 I .感谢 Aashish Barnwal 提出这种方法。 下面的代码只是针对算法的第二步，它假设数组已经排序了。
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?php
// PHP program to find a pair with
// the given difference
// The function assumes that the
// array is sorted
function findPair(&$arr, $size, $n)
{
// Initialize positions of
// two elements
$i = 0;
$j = 1;
// Search for a pair
while ($i < $size && $j < $size)
{
if ($i != $j && $arr[$j] -
$arr[$i] == $n)
{
echo "Pair Found: " . "(" .
$arr[$i] . ", " . $arr[$j] . ")";
return true;
}
else if ($arr[$j] - $arr[$i] < $n)
$j++;
else
$i++;
}
echo "No such pair";
return false;
}
// Driver Code
$arr = array(1, 8, 30, 40, 100);
$size = sizeof($arr);
$n = 60;
findPair($arr, $size, $n);
// This code is contributed
// by ChitraNayal
?>
输出:
Pair Found: (40, 100)
哈希也可以用来解决这个问题。创建一个空哈希表 HT。遍历数组，使用数组元素作为哈希键，并在 HT 中输入它们。再次遍历数组，在 HT 中寻找值 n + arr[i]。
更多详情请参考整篇文章找到一对给定差异的！
版权属于：月萌API www.moonapi.com，转载请注明出处
