[codility] Time Complexity- PermMissingElem

문제 

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

function solution(A: array of longint; N: longint): longint;

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

N개의 서로 다른 정수로 구성된 배열 A 제공

[1..(N+1)] 누락된 값을 구하기 

 

구현 해설

- 정렬

- 배열 순회하면서 $0, $1 비교해서 값이 다르면 순차값이 아니기때문에 해당 인덱스+1로 틀린값을 반환

- 인덱스+1과 0번째 배열값을 비교해서 다르면 인덱스 + 1로 누락값을 리턴

 

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)

	A.sort()

    for (index, _) in A.enumerated() {
        if index+1 != A[index] {
            return index+1
        }
    }

    return A.count+1
}