我最近不得不做一个代码挑战，其中指示我，对于一组数字，找到差值为K的对数。例如，给定数字1, 5, 3, 4, 2和差值K（2），有3对：（5,3）（4,2）（3,1）。我在PHP中尝试过这个挑战。我的代码通过了测试，但我想效率很低，因为有些测试超时了。有人能告诉我我是怎么改进的吗？我很头疼，因为我不知道如何才能让它更有效率。
这是我的代码
<?php
// Open STDIN for reading
$stdin = fopen('php://stdin', 'r');
// Get the input
while(!feof($stdin)) {
$inputs[] = explode(' ', fgets($stdin));
}
fclose($handle);
$k = $inputs[0][1];
$values = array_map('intval', array_values($inputs[1]));
// Sort in decending order
rsort($values);
// Given the difference, K, find a pair for $left within
// $right whose difference is K
function findPair($k, $left, $right){
foreach($right as $n) {
if($left - $n == $k)
return $n;
// If the difference is greater than $k, there is no pair
if($left - $n > $k)
return false;
}
return false;
}
$pairs = 0;
while(count($values) > 1){
$left = array_shift($values);
$n = findPair($k, $left, $values);
if($n !== false)
$pairs++;
}
echo $pairs;
?>
您的代码具有O(n^2)复杂性，因此在大型数据集上效率低下。它是O(n^2)，因为您在函数内部循环所有具有foreach的数组，并在外部循环的while中调用它。
但是你可以很容易地用O(n x log(N)):
function binSearch($array, $value, $from=null, $till=null)
{
$from = isset($from)?$from:0;
$till = isset($till)?$till:count($array)-1;
if($till<$from)
{
return null;
}
$middle = (int)($from + ($till - $from)/2);
if($array[$middle]>$value)
{
return binSearch($array, $value, $from, $middle-1);
}
if($array[$middle]<$value)
{
return binSearch($array, $value, $middle+1, $till);
}
return $middle;
}
$data = [1, 5, 3, 4, 2];
$k = 2;
sort($data); //O(n x log(n))
$count = 0;
foreach($data as $value) //O(n)
{
$count += null===binSearch($data, $value+$k)?0:1;//O(log(N))
}
var_dump($count);
-因此，您将使用具有O(n log(n))复杂度的标准sort()，然后使用二进制搜索N次。二进制搜索有O(log(n)) complexity，所以循环复杂度也将是O(n log (n))。因此，整个代码的复杂度将为O(n log(n)) + O(n log(n)) = O(n log(n))。
注意：标准PHP的in_array()具有O(N)复杂度，因此使用它将产生循环的O(N^2)复杂度估计，因此产生O(N^2)代码复杂度。
注意：通过sort()排序将产生快速排序。该算法具有O(n log(n))平均复杂度，最坏的情况是O(N^2)，因此可能存在数据集的情况，对于这些情况，上面的代码可能也是低效的。您可以研究其他排序算法。例如，如果你的问题是时间限制，你可以尝试合并排序——它会非常快（但会占用额外的空间）。
注意：如果我们谈论的是时间复杂性和空间复杂性并不重要，那只是可以使用的简单哈希图。在PHP中，它只是数组：
$array = [1, 5, 3, 4, 2];
$k = 2;
$count = 0;
$map = [];
foreach ($array as $number) //O(n) time
{
$map[$number] = $number;
}
foreach($map as $key=>$nevermind) //O(n) time
{
//O(1) if there are no duplicates, very close to O(1) otherwise
$count += array_key_exists($key+$k, $map);
}
var_dump($count);
-这将导致CCD_ 20的时间复杂度和CCD_。