Swift Dictionary很慢吗?

2cmtqfgy  于 2022-10-31  发布在  Swift
关注(0)|答案(1)|浏览(159)

Situation:我正在解决LeetCode 3. Longest Substring Without Repeating Characters,当我使用Dictionary和Swift时,结果是Time Limit Exceeded,未能通过最后一个测试用例,但使用与C++相同的代码概念,它实际上通过了运行时,一切正常。我认为在Swift中,DictionaryUnorderdMap是一样的。
Some research:我发现一些资源说使用NSDictionary而不是常规的,但它需要引用类型而不是Int或Character等。
Expected result:在Swift中访问Dictionary时的快速性能
我知道这个问题有更好的答案,但这里的主要目标是Is there a effiencient to access and write to Dictionary或我们可以用来替代的东西。

func lengthOfLongestSubstring(_ s: String) -> Int {
        var window:[Character:Int] = [:] //swift dictionary is kind of slow?
        let array = Array(s)
        var res = 0
        var left = 0, right = 0
        while right < s.count {
            let rightChar = array[right]
            right += 1
            window[rightChar, default: 0] += 1
            while window[rightChar]! > 1 {
                let leftChar = array[left]
                window[leftChar, default: 0] -= 1
                left += 1
            }
            res = max(res, right - left)
        }
        return res
    }
zfycwa2u

zfycwa2u1#

O(n)时间复杂度O(n +1),所以你要把count保存在一个变量里。你可以在Strings and Characters in Swift Book章节阅读
扩展的字素簇可以由多个Unicode标量组成。这意味着不同的字符(以及同一字符的不同表示)可能需要不同的内存量来存储。因此,Swift中的每个字符在字符串表示中占用的内存量并不相同。因此,如果不对字符串进行迭代以确定其扩展的字形簇边界,就无法计算字符串中的字符数。如果处理的字符串值特别长,请注意count属性必须迭代整个字符串中的Unicode标量以确定该字符串的字符。
count属性返回的字符数并不总是与包含相同字符的NSString的length属性相同。NSString的长度基于字符串的UTF-16表示形式中16位代码单元的数量,而不是字符串中Unicode扩展字形簇的数量。

相关问题