Есть ли сложность инициализации массива из набора, и если да, то что это?

Question

Swift: вариант 1

var dictionaryWithoutDuplicates = [Int: Int]()
for item in arrayWithDuplicates {
   if dictionaryWithoutDuplicates[item] == nil {
      dictionaryWithoutDuplicates[item] = 1
   }
}
print(dictionaryWithoutDuplicates.keys)
// [1,2,3,4]

Вариант 2

let arrayWithDuplicates = [1,2,3,3,2,4,1]
let arrayWithoutDuplicates = Array(Set(arrayWithDuplicates))
print(arrayWithoutDuplicates)
// [1,2,3,4]

Для первого варианта может быть более элегантный способ сделать это, но это не моя точка зрения, я просто хотел показать пример со сложностью n. Оба варианта возвращают массив без дубликатов. Поскольку первый вариант имеет сложность O (n), мне было интересно, если второй вариант имеет даже сложность, и если да, то что это?

Answer 1

То, что вы сделали, в значительной степени точно то, что делает Set.Set<T> - это всего лишь [T: Void] (он же Dictionary<T, Void>).

Оба примера имеют O(arrayWithDuplicates.count) сложность времени и пространства.