我最近做了一个code挑战，我在那里指示，对一组数字，找到对的差异K.例如数量，然后给予编号 1，5 ，3，4，2 ，系统和差值K（2）有3对：（5,3）（4,2）（3,1）。我试图在PHP这一挑战。我的code通过了测试，但效率不高我猜是因为一些测试超时。谁能告诉我，我怎么能提高呢？我扑我的头，因为我想不通我怎么可以使之更有效率。

下面是我的code

 ＆LT; PHP
    //打开STDIN阅读
    $标准输入=的fopen（'php的：//标准输入'，'R'）;

    //获取输入
    而（！的feof（$标准输入））{
        $输入[] =爆炸（''，与fgets（$标准输入））;
    }
    fclose函数（$处理）;

    $ K ​​= $输入[0] [1];
    $值= array_map（'INTVAL'，array_values​​（$输入[1]））;

    //排序的降序排列
    rsort（$值）;

    //由于差异，K，发现一对为$内左
    // $权其差值为K
    功能findPair（$ K，$左，右$）{
        的foreach（$权为$ N）{
            如果（$左 -  $ N == $ K）
                返回$ N;
            //如果差大于$ K，没有对
            如果（$左 -  $ N＆GT; $ K）
                返回false;
        }

        返回false;
    }

    $对= 0;

    而（计数（$值）→1）{
        $左= array_shift（$值）;
        $ N = findPair（$ K，$左，$值）;

        如果（$ N！==虚假）
            $双++;
    }

    回声$对;
？＆GT;
 

解决方案

您code具有为O（n ^ 2）复杂 - 所以这将是低效对大型数据集。这是为O（n ^ 2），因为你通过所有的数组循环与的foreach 您的函数中，并调用它，而外循环。

不过，你可以很容易做的东西 0（NX的log（n））：

 函数BINSEARCH（$数组，$值，从= NULL，$ $直到= NULL）
{
   从$ =使用isset（$距离）$来源：0;
   $直到=使用isset（$到）$到：计数（$阵列）-1;
   如果（$至＆LT; $从）
   {
      返回null;
   }
   $中间=（INT）（$由+（$到 -  $从）/ 2）;
   如果（$数组[$中间]＆GT; $值）
   {
      返回BINSEARCH（$阵列，$值，从$，$中间-1）;
   }
   如果（$数组[$中间]＆LT; $值）
   {
      返回BINSEARCH（$数组，$值，$中间+ 1，$至）;
   }
   返回$中间;
}

$数据= [1，5，3，4，2];
$ K ​​= 2;

排序（$的数据）; // O（的N×的log（n））
$计数= 0;

的foreach（$数据$值）//为O（n）
{
   $计数+ = NULL === BINSEARCH（$数据，$值+ $ K）？0：1; // O（日志（N））
}
后续代码var_dump（$计数）;
 

- 所以，你会使用标准的 的sort（） 与 O（N日志（N））的复杂性，然后用二进制搜索 N 次。二进制搜索有 O（日志（N））的复杂性，所以循环的复杂性也将 O（N日志（N））。因此，整个code的复杂性将是 O（N日志（N））+ O（N日志（N））= O（N日志（N））。

注意：的标准的PHP的 in_array（） 有 O（N）复杂 ，所以使用它会产生 O（N ^ 2）的复杂性估计的循环，因此， O（N ^ 2） code的复杂性。

注意：的通过排序排序（）将产生的快速排序。该算法 O（N日志（N）） 平均的复杂性，这是最坏的情况是 O（N ^ 2） - 所以有可能是数据集的情况下，对其中code以上内容可能也无效率。你可以看看其他排序算法的。例如，如果你的问题是时间限制，你可以尝试归并排序 - 这将是非常快（但是这将需要额外的空间）。

注意：如果我们谈论的时间复杂度和空间复杂度都无所谓，它只是简单的散列图，都可以使用。在PHP它只是数组：

  $阵列= [1，5，3，4，2]。
$ K ​​= 2;

$计数= 0;
$地图= [];

的foreach（$数组作为$号）// O（n）的时间
{
   $图[$数= $编号;
}
的foreach（$地图为$关键=＆GT; $没关系）// O（n）的时间
{
   // O（1）如果没有重复的，非常接近O（1），否则
   $计数+ = array_key_exists（$键+ $ K，$图）
}

后续代码var_dump（$计数）;
 

- 将要导致 O（N）时间复杂度和 O（2N）= O（N）空间复杂度。

I recently had to do a code challenge where I was instructed that for a set of numbers, find the number of pairs whose difference was K. For example, given then numbers 1, 5, 3, 4, 2, and the difference K (2) there are 3 pairs: (5,3) (4,2) (3,1). I tried this challenge in PHP. My code passed the test, but was inefficient i guess because some of the test timed out. Can anyone tell me how I could have improved it? I'm bashing my head because I can't figure out how I could make it more efficient.

Here's my code

<?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;
?>

Your code have O(n^2) complexity - and so it will be inefficient on large data sets. It's O(n^2) since you're looping through all array with foreach inside your function and calling it in while in external loop.

But you can easily do the stuff with 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);

-so, you will use standard sort() with O(n log(n)) complexity and then use binary search N times. Binary search has O(log(n)) complexity, so loop complexity will be also O(n log (n)). Therefore, whole code complexity will be O(n log(n)) + O(n log(n)) = O(n log(n)).

Note: standard PHP's in_array() has O(N) complexity, so using it will produce O(N^2) complexity estimation for loop, and, therefore, O(N^2) code complexity.

Note: sorting via sort() will produce quick sorting. This algorithm has O(n log(n)) average complexity, it's worst case is O(N^2) - so there may be cases of data sets, for which code above may be also inefficient. You may look into other sorting algorithms. For example, if your problem is time limit, you may try merge sort - it will be extremely faster (but it will take additional space).

Note: If we're speaking about time complexity and space complexity does not matter, it's just simple hash-map that can be used. In PHP it's just array:

$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);

-that will result in O(n) time complexity and O(2n)=O(n) space complexity.