我第一次做代碼測試，30分鐘沒解決這個問題。您能給我解決此代碼測試的答案之一嗎？寫一個函數(shù)：function solution($A);給定一個包含 N 個整數(shù)的數(shù)組 A，返回 A 中未出現(xiàn)的最小正整數(shù)（大于 0）。例如給定A = [1, 3, 6, 4, 1, 2]，該函數(shù)應(yīng)該返回5。鑒于此A = [1, 2, 3]，該函數(shù)應(yīng)該返回4。鑒于此A = [?1, ?3]，該函數(shù)應(yīng)該返回1。為以下假設(shè)編寫一個有效的算法：N 是范圍內(nèi)的整數(shù)，[1..100,000];數(shù)組 A 的每個元素都是范圍內(nèi)的整數(shù)[?1,000,000..1,000,000]。
1 回答
慕后森
TA貢獻(xiàn)1802條經(jīng)驗 獲得超5個贊
我確信有一種更有效的方法可以完成它，但這里有一些可以幫助您繼續(xù)下去的方法。它仍然會循環(huán)最多 100,000 次，這已經(jīng)是相當(dāng)多了。
function solution($array) {
$i = 1;
while (in_array($i, $array)) $i++;
return $i;
}
編輯：這是一個更優(yōu)化的解決方案，不使用in_array：
function solution($array) {
// sort from smallest to largest
sort($array);
// try to find a positive break in the sequence
$last = 0;
if (end($array) > 0) {
foreach ($array as $current) {
if ($current == $last) continue; // duplicate
if ($current != $last + 1 && $current > 0) break;
$last = $current;
}
}
return $last + 1;
}
- 1 回答
- 0 關(guān)注
- 94 瀏覽
添加回答
舉報
0/150
提交
取消