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

Question

我知道使用 remove(at:).

从 Swift 数组中删除一个项目通常需要 O(n) 时间

假设我有这样的代码：

// 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

如果 myArray 不包含具有重复 ID 的项目，您可以使用 removeAll(where:) 而不是双 for 循环：

myArray.removeAll(where: { item in 
    refArray.contains { [=10=].id == item.id }
})

这是 O(n*m)，其中 n 和 m 分别是 myArray 和 refArray 的大小。

否则，您可以按照starboy_b在评论中所说的那样，收集所有索引并使用remove(atOffsets:)一次性删除它们：

var indicesToRemove = IndexSet()
for refItem in refArray {
    for (index, item) in myArray.enumerated() {
        if i == j, !indicesToRemove.contains(index) {
            indicesToRemove.insert(index)
            break
        }
    }
}
myArray.remove(atOffsets: indicesToRemove)

这也是 O(n*m)。

Answer 2

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

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

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

然后

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) 我们可以增加算法的 space 复杂度。简而言之，我们牺牲 space 复杂性来提高时间复杂性。

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

How to get O(1) time complexity for Array.remove(at:) in Swift

arrays

algorithm

time-complexity

swift