[Swift] Codility Lesson 4 - MissingInteger

문제

This is a demo task.

Write a function:

public func solution(_ A : inout [Int]) -> Int

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

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].

 

문제 링크

MissingInteger coding task - Learn to Code - Codility

GitHub

GitHub - yoohyebin/swift

 

문제 분석

• N개의 정수로 이루어진 배열 A가 주어지면, A에 없는 가장 작은 양의 정수(0보다 큼)를 반환한다.

ex)
A = [1, 3, 6, 4, 1, 2]  5
A = [1, 2, 3]              4
A = [-1, -3]               1

 

해결방안

1. 입력된 배열 A의 최댓값이 0보다 작다면 모두 음수로 구성된 배열이기 때문에 1을 반환
2. 1부터 N(A.count)까지 정수들로 구성된 Set(집합) 생성
3. Set과 A의 차집합이 존재하면 차집합중 작은 값을 반환, 없다면 N+1 반환

Solution

public func solution(_ A : inout [Int]) -> Int {
    if A.max()! <= 0 {
        return 1
    }
    let setB = Set(1...A.count)

    if let re = setB.subtracting(A).min(){
        return re
    }else{
        return A.count+1
    }
}

• 시간 복잡도: O(N) or O(N * log(N))