[Codility] 4. MissingInteger

8246 ワード
codility Counting Elements テキストリンク

[Codility] 4. MissingInteger


質問リンク


MissingInteger

問題の概要


整数からなる配列Aが与えられると、Aに含まれない最小の整数が返される--ほほほ
例
A = [1, 3, 6, 4, 1, 2] return 5
A = [1, 2, 3] return 4
A = [−1, −3] return 1

要求


N is an integer within the range [1..100,000]
each element of array A is an integer within the range [−1,000,000..1,000,000]

イニシャルコード


O(N**2)の無意識コードㅠㅠ
Aは陰、陽の整数に分けて、それぞれ陰、陽の韁皓に盛る
正の整数に何もない場合は、負の整数しかないので返します.
そして再びforを含む...
O(N*2)は予想された.ああ...ほほほ
import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var posArr: [Int] = []
    var negArr: [Int] = []
    var ans = Int()

    A.forEach { //O(N)
        if($0 > 0) {
            posArr.append($0)
        } else {
            negArr.append($0)
        }
    }
    if(posArr.count == 0) {
        return 1
    }

    for i in 1...posArr.count { //O(N)
        if(posArr.contains(i)) {
            ans = posArr[i-1] + 1
            continue
        } else {
            return i
        }    
    }
    return ans
}

完了コード

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var setNum = Set<Int>(A)
    var ansVal = Int()
    
    for idx in 1...A.count {
        if !setNum.contains(idx) {
            return idx
        } else {
            ansVal = idx + 1
            continue
        }
    }
    return ansVal
}
ずっとタイムアウト解を表示していて、検索時間の複雑さが解けて、2時間もかかったようです.
Setのcontains時間の複雑さはなんとO(1)...
ArrayはO(N)です

時間の複雑さも整理しておきましょう.
玄涛は一日...ははは
UE4 Character adding Camera & CameraBoom
Drools学習ノート2