Swift - Set (Array) выделяет дополнительное пространство?

Question

Я работал над вопросом Leetcode вчера. Это описывается следующим образом:

С учетом нумерации отсортированного массива удалите дубликаты на месте, чтобы каждый элемент появлялся только один раз, и возвращали новую длину.

Не выделяйте лишние пространство для другого массива, вы должны сделать это, изменив входной массив на месте с помощью O (1) дополнительной памяти.

А вот мое решение в Swift, так как для него требуется in-place with O(1) extra memory, мой вопрос в том, что Set(nums) требует дополнительной памяти, если да, сколько это займет?

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        nums = Array(Set(nums))
        nums.sort() {$0 < $1}
        print(nums)
        return nums.count
    }
}

Answer 1

Да, Set(nums) выделяет дополнительную память. Он может быть таким же большим, как и сам массив, если все исходные значения уникальны.

O (1) память означает, что ваш алгоритм будет выделять только постоянный объем дополнительной памяти (вероятно, только 4 или 5 переменных), что не зависит от размера входного массива. Представьте разницу в объеме памяти, который ваш алгоритм будет использовать, когда входной массив имеет 10 значений и когда он имеет 10 000 значений. Set будет занимать гораздо больше памяти во втором случае, поэтому это не O (1).

Подсказка: используйте тот факт, что массив отсортирован для обнаружения дубликатов.