3 回答

TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超22個(gè)贊
看起來(lái)您的數(shù)組A不包含任何正數(shù)。因此你的循環(huán)不會(huì)中斷。
O(n log n)解決方案:
public int solution(int[] A) {
final int solution[] = {1};
Arrays.stream(A)
.filter(i -> i > 0)
.sorted()
.forEach(i -> {
if (i == solution[0]) {
solution[0]++;
}
});
return solution[0];
}
O(n)解決方案:
public int solution2(int[] A) {
BitSet bitSet = new BitSet();
Arrays.stream(A)
.filter(i -> i > 0)
.forEach(bitSet::set);
return bitSet.nextClearBit(1);
}

TA貢獻(xiàn)1946條經(jīng)驗(yàn) 獲得超4個(gè)贊
您有一個(gè)效率低下的 O(N*m) 算法。
我建議使用不同的策略,只傳遞一次數(shù)組。O(n) 例如使用 BitSet 來(lái)記錄存在哪些正數(shù)。然后找到 BitSet 中第一個(gè)缺失的條目。例如BitSet.nextBitClear(1)
一個(gè)更簡(jiǎn)單的解決方案是對(duì)數(shù)組進(jìn)行排序并找到第一個(gè)丟失的元素,但是,這是 O(n ln n),它較慢但可能足夠快。

TA貢獻(xiàn)1811條經(jīng)驗(yàn) 獲得超4個(gè)贊
對(duì)于有效的解決方案,您應(yīng)該考慮對(duì)于任何解決方案n,數(shù)組必須至少包含所有n-1正數(shù),因此長(zhǎng)度必須至少為n-1。這反過(guò)來(lái)又允許得出結(jié)論,解決方案永遠(yuǎn)不會(huì)大于數(shù)組長(zhǎng)度加一。
所以我們必須記錄的,是小于這個(gè)限制的正數(shù)。此外,超出該范圍的每個(gè)值都會(huì)減少可用于n-1 個(gè)元素的數(shù)組元素的數(shù)量,因此,我們可以進(jìn)一步縮小范圍。
正如 Peter Lawrey 所建議的,您可以使用 aBitSet來(lái)記錄可能的解決方案范圍內(nèi)遇到的值。此類(lèi)還有一個(gè)高效的內(nèi)置操作,用于查找與最小未遇到值匹配的第一個(gè)清除位。
public int solution(int[] a) {
int limit = a.length;
BitSet encountered = new BitSet();
for(int value: a)
if(value < 1 || value > limit) limit--; else encountered.set(value);
return encountered.nextClearBit(1);
}
添加回答
舉報(bào)