如果一个单词由唯一的字母组成(不区分大小写),我需要检查
Java.因为直接的解决方案是无聊的,我想出了：
>对于字符串中的每个字符串,检查indexOf(char)== lastIndexOf(char).
>将所有字符添加到HashSet,并检查是否设置size == string length.
>将字符串转换为字符数组,按字母顺序排序,循环遍历数组元素,并检查c [i] == c [i 1].
解决方法
我不喜欢1. – 这是一个O(N2)算法.你的2.大致是线性的,但总是遍历整个字符串.您的3.是O(N lg2 N),(可能)相对较高的常数 – 可能几乎总是比2慢.
但是,当您尝试在集合中插入一个字母,检查它是否已经存在时,我的偏好是,您可以立即停止.给定随机分配的字母,这应该只需要平均扫描一半的字符串.
编辑：两个注释都是正确的,正是您期望扫描的字符串的哪个部分将取决于分布和长度 – 在某些时候,字符串足够长,重复是不可避免的,(例如)一个字符不足那机会还是很高的.事实上,给定一个平坦的随机分布(即集合中的所有角色同样可能),这应该与生日悖论密切相关,这意味着碰撞的机会与可能的字符数的平方根有关字符集.例如,如果我们以相同的概率假设基本的US-ASCII(128个字符),我们将在大约14个字符处达到50％的碰撞几率.当然,在真正的字符串中,我们可能比它早一些,因为ASCII字符在大多数字符串中的任何接近于相同频率的位置都不被使用.
