这个答案 https://stackoverflow.com/a/36818947/2642059通过比较两个字符串的内容来确定它们是否是排列。如果它们包含相同数量的每个字符，那么它们显然是排列。这是在O(N) time.
但我不喜欢这个答案，因为它重新发明了什么is_permutation http://en.cppreference.com/w/cpp/algorithm/is_permutation是设计来做的。也就是说，is_permutation其复杂度为：
At most O(N2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1)
So I cannot advocate the use of is_permutation where it is orders of magnitude slower than a hand-spun algorithm. But surely the implementer of the standard would not miss such an obvious improvement? So why is is_permutation O(N2)?
is_permutation适用于几乎任何数据类型。您链接中的算法仅适用于具有少量值的数据类型。
这也是同样的原因std::sort是 O(N log N) 但计数排序是 O(N)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
