arrays - 如何获得 Array.remove(at :) in Swift) 的 O(1) 时间复杂度

Question

我知道通常需要 O(n) 的时间来使用 remove(at:) 从 Swift 数组中删除一个项目。

假设我有这样的代码:

// refArray has m elements
// myArray has n elements

for refItem in refArray {
    for (index, item) in myArray.enumerated() {
        if item.id == refItem.id {
            <Do something>
            myArray.remove(at: index)
            break
        }
    }
}

对于 myArray.remove(at: index)，即使我已经知道要删除的项目的索引，但是如果我 使用remove(at:)，仍然需要O(n)的时间。 所以整个过程可能需要 O(n³) 时间。

有什么方法可以使它成为 O(n²)，但当 item.id == refItem.id 时仍然从 myArray 中删除一个项目？

Answer 1

如果您想从 n 项数组中删除 m 项，是的，您可以重构它以实现 O(m*n) 时间复杂度。但是每当您看到嵌套的 for 循环(或等同于同一事物的嵌套函数)时，您应该考虑是否有可以构建的结构将 O(m*n) 减少到 O (m+n)，速度显着加快。

在这种情况下，我们确实有这样的机会。因此，我们首先构建一个我们将要搜索的值的散列结构。然后我们可以遍历数组一次查找要删除的记录，每个记录的复杂度为 O(1)。正如其他地方所讨论的，我们可以使用类似 removeAll(where:) 的方法，而不是让您自己的 for 循环调用 remove(at:)将执行此循环并在 O(n) 复杂度的一步中删除所有内容。

extension Array where Element: Hashable {
    mutating func remove(values: [Element]) {
        let set = Set(values)
        removeAll { set.contains($0) }
    }
}

然后

var array = [0, 1, 2, 3, 4, 5, 6]
var values = [1, 3, 5]
array.remove(values: values)
print(array)                       // [0, 2, 4, 6]

主题有很多变体，但想法大体相同:如果可以，构建一个结构，在 O(1) 时间内识别要删除的值。然后你可以只遍历数组一次，例如使用 removeAll。最终结果是总体 O(m+n) 时间复杂度，这比您的原始算法或预期的 O(m*n) 演绎版快得多。

请注意，如果 (a) 数组中的元素是 Hashable； (b) 我们可以增加算法的空间复杂度。简而言之，我们通过牺牲空间复杂度来提高时间复杂度。