簡單的PHP程序需要更少的時間來執行

-1

我最近申請了一份工作，要求完成一個測試，然後採訪 2個問題給出了非常簡單的測試，我成功地完成了，但仍然被告知我沒有通過測試，因爲腳本花了超過18秒才完成執行。這裏是該程序，我不明白我還能做些什麼來使它快速。雖然我沒有通過測試，但仍然想知道我可以做什麼？編程語言是PHP和我所要做的使用命令行輸入簡單的PHP程序需要更少的時間來執行

這是個問題：

K Difference 
Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9] 

Input Format: 
1st line contains N & K (integers). 
2nd line contains N numbers of the set. All the N numbers are assured to be distinct. 
Output Format: 
One integer saying the no of pairs of numbers that have a diff K. 

Sample Input #00: 
5 2 
1 5 3 4 2 

Sample Output #00:3 
Sample Input #01: 
10 1 
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01: 
0 
Note: Java/C# code should be in a class named "Solution" 
Read input from STDIN and write output to STDOUT.

，這是解決

$fr = fopen("php://stdin", "r"); 
$fw = fopen("php://stdout", "w"); 

fscanf($fr, "%d", $total_nums); 
fscanf($fr, "%d", $diff); 

$ary_nums = array(); 
for ($i = 0; $i < $total_nums; $i++) { 
    fscanf($fr, "%d", $ary_nums[$i]); 
} 

$count = 0; 
sort($ary_nums); 
for ($i = $total_nums - 1; $i > 0; $i--) { 
    for ($j = $i - 1; $j >= 0; $j--) { 
     if ($ary_nums[$i] - $ary_nums[$j] == $diff) { 
      $count++; 
      $j = 0; 
     } 
    } 
} 
fprintf($fw, "%d", $count);

來源

2013-07-25 Wasif Khalil

你的算法的運行時間爲O（N^2）約爲10^5 * 10^5 = 10^10。有了一些基本的觀察，它可以減少到O（NlgN），它僅僅是大約10^5 * 16 = 1.6 * 10^6。

算法：

排序陣列ary_nums。
對於數組中的每個第i個整數，進行二進制搜索以查找ary_nums [i] -K是否存在於數組中。如果出現增加結果，則跳過第i個整數。

sort（$ ary_nums）;

for ($i = $total_nums - 1; $i > 0; $i--) { 

     $hi = $i-1; 
     $low = 0; 
     while($hi>=$low){ 
      $mid = ($hi+$low)/2; 
      if($ary_nums[$mid]==$ary_nums[$i]-$diff){ 
       $count++; 
       break; 
      } 
      if($ary_nums[$mid]<$ary_nums[$i]-$diff){ 
       $low = $mid+1; 
      } 
      else{ 
       $hi = $mid-1; 
      } 
     } 
    } 
}

來源

2013-07-25 05:17:17 Fallen

我在技術面試中遇到了同樣的問題。我想知道我們是否正在面試同一家公司。 :)

總之，這裏是我的答案，我想出了（採訪後）：

// Insert code to get the input here 

$count = 0; 
sort ($arr); 

for ($i = 0, $max = $N - 1; $i < $max; $i++) 
{ 
    $lower_limit = $i + 1; 
    $upper_limit = $max; 

    while ($lower_limit <= $upper_limit) 
    { 
     $midpoint = ceil (($lower_limit + $upper_limit)/2); 
     $diff = $arr[$midpoint] - $arr[$i]; 

     if ($diff == $K) 
     { 
     // Found it. Increment the count and break the inner loop. 
     $count++; 
     $lower_limit = $upper_limit + 1; 
     } 
     elseif ($diff < $K) 
     { 
     // Search to the right of midpoint 
     $lower_limit = $midpoint + 1; 
     } 
     else 
     { 
     // Search to the left of midpoint 
     $upper_limit = $midpoint - 1; 
     } 
    } 
}

@Fallen：您的代碼失敗以下輸入：

Enter the numbers N and K: 10 3 
Enter numbers for the set: 1 2 3 4 5 6 7 8 9 10 
Result: 6

我認爲它與你的$mid（不佔奇數）的計算有關

來源

2013-08-01 16:20:33 Sutandiono

簡單的PHP程序需要更少的時間來執行

回答

相關問題