我第一次做代碼測試，30分鐘沒解決這個問題。您能給我解決此代碼測試的答案之一嗎？寫一個函數：function solution($A);給定一個包含 N 個整數的數組 A，返回 A 中未出現的最小正整數（大于 0）。例如給定A = [1, 3, 6, 4, 1, 2]，該函數應該返回5。鑒于此A = [1, 2, 3]，該函數應該返回4。鑒于此A = [?1, ?3]，該函數應該返回1。為以下假設編寫一個有效的算法：N 是范圍內的整數，[1..100,000];數組 A 的每個元素都是范圍內的整數[?1,000,000..1,000,000]。
1 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
我確信有一種更有效的方法可以完成它，但這里有一些可以幫助您繼續下去的方法。它仍然會循環最多 100,000 次，這已經是相當多了。
function solution($array) {
$i = 1;
while (in_array($i, $array)) $i++;
return $i;
}
編輯：這是一個更優化的解決方案，不使用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 關注
- 89 瀏覽
添加回答
舉報
0/150
提交
取消