Codility - FrogRiverOne - Swift

Question

我正在尝试为以下可调节任务找到最佳 swift 解决方案，请分享您的观点。

时间复杂度 - O(N**2)

任务描述

一只小青蛙想去河对岸。青蛙最初位于河的一岸（位置 0），想要到达对岸（位置 X+1）。叶子从树上落到河面上。

给你一个数组A，由N个表示落叶的整数组成。 A[K]表示一片叶子在时间K落下的位置，以秒为单位。

目标是找出青蛙最早能跳到河对岸的时间。只有当从1到X过河的每个位置都出现树叶时，青蛙才能过河（即我们要找到从1到X的所有位置都被树叶覆盖的最早时刻）。你可以假设河流中的水流速度很小，可以忽略不计，即叶子落入河流后不会改变位置。

例如，给定整数 X = 5 和数组 A 使得：

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

第6秒，一片树叶落在第5个位置，这是过河各个位置出现树叶最早的时间。

写一个函数：

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

即，给定一个由N个整数和整数X组成的非空数组A，return是青蛙能跳到河对岸的最早时间。

如果青蛙永远无法跳到河的另一边，函数应该return −1.

例如，给定 X = 5 和数组 A 使得：

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

函数应该 return 6，如上所述。

为以下假设编写一个有效的算法：

N and X are integers within the range [1..100,000]; each element of array A is an integer within the range [1..X].

编辑 - 错过了添加我的方法，感谢您强调它，非常感谢您抽出时间。合十礼

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    let destination  = X
    var positionDict = [Int: Bool]()
        
    for (index,value) in A.enumerated() {
        if value <= destination, positionDict[value] == nil  {
            positionDict[value] = true
        }
        if hasPositions(initial: A[0], destination: X, dict: positionDict) {
            return index
        }
    }
    return -1
}

func hasPositions(initial: Int, destination: Int, dict: [Int: Bool]) -> Bool {
    for i in stride(from: initial, to: destination+1, by: 1 ) {
        if dict[i] == nil {
            return false
        }
    }
    return true
}

var arr = [1,3,1,4,2,3,5,4]
print(solution(5, &arr))

//CODILITY gave 45 % for the solution, please share where am i going wrong.

Answer 1

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
  typealias  = [Int]
  typealias  = EnumeratedSequence<>
  let  = .first
  let  = 1
  var  = Set(...X)

  return try!
    (A.enumerated()) ({
        .remove([=10=].element)
        return .isEmpty
      })?
      .offset
    ?? -
}