java – 检查字符串是否由唯一字符组成的最简单的方法?
如果一个单词由唯一的字母组成(不区分大小写),我需要检查
Java.因为直接的解决方案是无聊的,我想出了:
>对于字符串中的每个字符串,检查indexOf(char)== lastIndexOf(char). 目前我最喜欢#2,好像最简单的方法.任何其他有趣的解决方案? 解决方法
我不喜欢1. – 这是一个O(N2)算法.你的2.大致是线性的,但总是遍历整个字符串.您的3.是O(N lg2 N),(可能)相对较高的常数 – 可能几乎总是比2慢.
但是,当您尝试在集合中插入一个字母,检查它是否已经存在时,我的偏好是,您可以立即停止.给定随机分配的字母,这应该只需要平均扫描一半的字符串. 编辑:两个注释都是正确的,正是您期望扫描的字符串的哪个部分将取决于分布和长度 – 在某些时候,字符串足够长,重复是不可避免的,(例如)一个字符不足那机会还是很高的.事实上,给定一个平坦的随机分布(即集合中的所有角色同样可能),这应该与生日悖论密切相关,这意味着碰撞的机会与可能的字符数的平方根有关字符集.例如,如果我们以相同的概率假设基本的US-ASCII(128个字符),我们将在大约14个字符处达到50%的碰撞几率.当然,在真正的字符串中,我们可能比它早一些,因为ASCII字符在大多数字符串中的任何接近于相同频率的位置都不被使用. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |