在PHP中使用PHP查找給定數組中缺少的數字

我剛剛接觸php，前幾天面試過，面試官問了一個像下面這樣的問題。在PHP中使用PHP查找給定數組中缺少的數字

給定數組有99個數字，其中包含從1到100的數字只有一個數字缺失。描述兩種不同的算法，找到你缺少的數字。算法應該針對低存儲和快速處理進行優化。輸出應顯示每個算法的執行時間。

我已經搜索了谷歌關於它，並知道它的一個常見的難題用於在採訪中要求。我找到了這樣的答案。

int sum = 0; 
int idx = -1; 
for (int i = 0; i < arr.length; i++) { 
    if (arr[i] == 0) { 
     idx = i; 
    } else { 
     sum += arr[i]; 
    } 
} 

// the total sum of numbers between 1 and arr.length. 
int total = (arr.length + 1) * arr.length/2; 

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

但代碼是不是在PHP中，

u能請幫我找出PHP代碼和算法的名字。所以我可以在接下來的採訪中提高我的答案。

來源

2014-03-31 user3480508

你嘗試轉換的是Java的代碼到PHP？它應該是相當直接的，當它說'arr.length'使用'count（$ arr）'時，其餘的應該幾乎相同。 – aurbano

在PHP中，您可以輕鬆使用一些數組函數並實現該功能。最好的辦法是，

$missing = array_diff(range(1,100),$array);

DEMO。

來源

2014-03-31 11:18:26 Rikesh

非常感謝您的快速回復。你知道任何適當的算法是否有計算這個？ – user3480508

你可以用*合適的算法*來定義你的意思嗎？ – Rikesh

@ user3480508如果您嘗試查找數組中缺少的元素，這是執行此操作的最簡單方法。但是，如果您正在尋找時間複雜度，與時間複雜度爲O（n）的線性/順序搜索相同。如果你知道需要搜索的元素，你可以應用其他好的算法，比如二進制搜索/插值搜索等，它們在複雜性方面要好得多。 –

另一種方式來做到這一點是通過使用array_sum功能以及從1到100的所有數字相加的知識等於5050

$missing = 5050-array_sum($array);

來源

2014-03-31 11:22:36

或者只是使用'range'來獲得5050：'$ missing = array_sum（range（1,100）） - array_sum（$ array）;' – Anthony

轉換爲PHP，它幾乎是相同的。（未測試）

當然，還有更好的方法，就像一個Rikesh發佈，但是這是你要的確切一個：

$sum = 0 
$idx = -1 
for($i = 0; $i < count($arr); $i++){ 
    if($arr[$i] == 0){ 
     $idx = $i; 
    }else{ 
     $sum += $arr[$i]; 
    } 
} 

$total = (count($arr) + 1) * (count($arr)/2); 

echo "Missing: " . ($total - $sum) . " at index " . $idx;

來源

2014-03-31 11:23:17 Bobby

感謝您的更正** Keir **。我一定錯過了這一個。 – Bobby

$arr=range(1,99); 
$j=1; 
for($i=0;$i<100;$i++){ 
if(!in_array($j,$arr)){ 
    echo $j.'is missing'; 
} 
$j++; 
}

來源

2015-05-28 06:55:18 Garima

在PHP中使用PHP查找給定數組中缺少的數字

回答

相關問題