превышение времени выполнения для решения пары разницы

Недавно мне пришлось выполнить вызов кода, где мне было поручено, чтобы для набора чисел находилось число пар, чья разница была 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; ?> 

Related of "превышение времени выполнения для решения пары разницы"

Ваш код имеет сложность O(n^2) – и поэтому он будет неэффективен для больших наборов данных. Это O(n^2) поскольку вы перебираете весь массив с помощью foreach внутри вашей функции и вызываете ее while внешнем цикле.

Но вы можете легко сделать материал с помощью O(nx 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(nx 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, вы будете использовать стандартную sort() с сложностью O(n log(n)) а затем используйте двоичный поиск 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); 

– это приведет к сложности времени O(2n)=O(n) сложности пространства O(2n)=O(n) .