第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題,去搜搜看,總會(huì)有你想問(wèn)的

為什么即使數(shù)組不是那么大,我為什么要執(zhí)行這個(gè)簡(jiǎn)單的任務(wù)卻得到 Timed out 錯(cuò)誤?

為什么即使數(shù)組不是那么大,我為什么要執(zhí)行這個(gè)簡(jiǎn)單的任務(wù)卻得到 Timed out 錯(cuò)誤?

幕布斯7119047 2022-01-06 18:58:46
我正在 codility.com 上執(zhí)行任務(wù),但出現(xiàn)超時(shí)錯(cuò)誤。代碼和任務(wù)描述如下。任務(wù)的文本(陣列被初始化):class Solution { public int solution(int[] A); }即,給定陣列A的N整數(shù),返回不發(fā)生在最小的正整數(shù)(大于0) A。例如,給定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è)編寫(xiě)一個(gè)有效的算法:N是 [1..100,000] 范圍內(nèi)的整數(shù);數(shù)組的每個(gè)元素A都是 [?1,000,000..1,000,000] 范圍內(nèi)的整數(shù)。class Solution {    public int solution(int[] A) {        int k;        for (int i = 1;; i++) {            final int j = i;            if (!Arrays.stream(A).anyMatch(x -> x != j)) {                k = j;                break;            }        }        return k;    }}
查看完整描述

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);

}


查看完整回答
反對(duì) 回復(fù) 2022-01-06
?
絕地?zé)o雙

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),它較慢但可能足夠快。


查看完整回答
反對(duì) 回復(fù) 2022-01-06
?
波斯汪

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);

}


查看完整回答
反對(duì) 回復(fù) 2022-01-06
  • 3 回答
  • 0 關(guān)注
  • 158 瀏覽
慕課專(zhuān)欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)