php - 超过对差挑战的执行时间限制

Question

我最近不得不做一个代码挑战，我被指示对于一组数字，找到差为 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;
?>

Answer 1

您的代码具有 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);

-因此，您将使用标准 sort() O(n log(n)) 复杂度，然后使用二进制搜索 N 次。二分查找具有 O(log(n)) 复杂度，因此循环复杂度也将是 O(n log (n))。因此，整个代码的复杂度将是 O(n log(n)) + O(n log(n)) = O(n log(n))。

注意:标准 PHP 的 in_array()有O(N) complexity ，因此使用它将产生 O(N^2) 循环的复杂性估计，因此，O(N^2) 代码复杂性。

注意:通过 sort() 排序将产生 quick sorting .该算法具有 O(n log(n)) 平均 复杂度，最坏的情况是 O(N^2) - 所以可能有数据集的情况，上面的代码也可能效率低下。您可以查看其他 sorting algorithms .例如，如果您的问题是时间限制，您可以尝试 merge sort - 它会非常快(但会占用额外的空间)。

注意:如果我们谈论时间复杂度和空间复杂度无关紧要，它只是可以使用的简单 HashMap 。在 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);

-这将导致 O(n) 时间复杂度和 O(2n)=O(n) 空间复杂度。