如果我们不执行实际的分配，它仍然是 O(n) space 吗？

Question

考虑 Valid Anagram 问题，我们 return true 如果两个字符串是彼此的变位词：

e.g. validAnagram("name", "mane") returns true.

假设我们只能按值传入字符串，一个可能的解决方案是将两个排序后的数组存储到新的变量中，然后return这些变量是否相等：

    func validAnagram(_ s: String, _ t: String) -> Bool {
        guard s.count == t.count else { return false }
        
        let sortedS = s.sorted()
        let sortedT = t.sorted()
     
        return sortedS == sortedT
    }

在这种情况下，算法的时间复杂度为O(nlogn)，复杂度为spaceO(2n) => O(n)

我的问题是将函数更改为以下内容是否会使 space 变得复杂 O(1):

func validAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else { return false }
    return s.sorted() == t.sorted()
}

这是真的吗？或者是否仍在后台分配内存以记住 s.sorted() 和 t.sorted() 是什么，即使我没有显式初始化变量？

Answer 1

这没有任何区别。您仍然为排序的数组分配内存。

为避免使用额外的 space，您需要尽可能对数据进行排序 in-place。

如果我们不执行实际的分配，它仍然是 O(n) space 吗？

Is it still O(n) space if we don't perform the actual assignment?

sorting

algorithm

swift