我试过 * 387.First Unique Character In A string *
给定一个字符串s,找到其中第一个不重复的字符并返回其索引。如果不存在,返回-1。
- 示例:1*
Input: s = "leetcode"
Output: 0
字符串
- 示例:2*
Input: s = "loveleetcode"
Output: 2
型
我一直在尝试这个问题。我想我们会一个接一个地选择所有的字符,并检查是否存在重复的字符,从循环中中断。如果没有,然后返回该索引。我已经想过一个解决方案,我认为这不是最有效的方法,但我想知道我如何解决这个问题,下面给出的方法:
public int firstUniqChar(String s) {
for(int i=0;i<s.length();i++){
for(int j=i+1;j<s.length();j++){
if(s.charAt(i)==s.charAt(j)){
break;
}
}
}
return -1;
}
型
我搞不懂怎么返回索引,找不到后面的逻辑:
for(int j=i+1;j<s.length();j++){
if(s.charAt(i)==s.charAt(j)){
break;
}
}
型
如果有人能帮我找出这里的逻辑。
8条答案
按热度按时间v7pvogib1#
试试这个.
字符串
产出:
型
mmvthczy2#
可以使用flag变量。
字符串
goucqfw63#
有26个可能的英文字母,所以你可以使用两个26元素数组。
一个数组
letterCount
保存每个字母的计数。从0开始,每当相应的字母出现在文本字符串中时加1。第二个数组position
保存该字母第一次出现的位置,或者如果该字母从未出现则为-1。您需要将该数组的所有元素初始化为-1。按顺序处理字符串,记录初始位置,每个字母只记录一次,并递增字符串中每个字母的计数。
处理完字符串后,查看
letterCount
数组。如果没有计数为1的字母,则返回-1。如果恰好有一个字母计数为1,则返回position
数组中该字母的位置。如果有多个字母计数为1,则选择其位置值最小的字母。使用两个循环是解决这个问题的一种非常低效的方法。字符串可以长达100,000个字符,并且您正在多次处理它。最好只处理一次,跟踪到目前为止找到的内容。
x33g5p2x4#
修复你的代码
您需要添加一个变量,告诉您是否已中断循环
字符串
提升
有一个更聪明的方法,那就是找到当前字符的最后一个索引,如果它等于当前索引:那个字符是唯一的,你返回它的索引
型
yjghlzjz5#
如果你不担心使用IdenxOF操作的时间复杂度,那么你可以尝试这个解决方案。
indexOf()-也是线性时间运行的。它遍历内部数组并逐个检查每个元素。因此此操作的时间复杂度始终需要O(n)时间。
字符串
ru9i0ody6#
我设法实现的最低复杂度:
字符串
我相信内存使用仍然可以优化。
u1ehiz5o7#
100%正确的JAVA解决方案
因为这个问题是关于返回字符串中第一个非重复字符的索引,所以我们需要一些数据结构来保存字符串中每个字符的索引。
这里我选择Java的HashMap。基本上,你可以用它做什么,你可以保存一对值(或一对其他数据结构)。
所以,在我的解决方案中,我保存了一个Character * 字符串对。第一个被认为是一个键(这里是字符串中的每个字符),第二个是它的索引值。
这里的问题是,我们只想保留非重复字符的最小索引,这就是为什么如果你看看下面,你会发现maxIndexForRepeatedValues被设置为10power5,因为输入约束说1 <= s.length <= 10 power 5。
然而,我使用这个值来忽略在HashMap中会找到的重复字符,最后,我们检索最小索引,当然是Map中第一个字符的索引,或者如果只有重复字符,我们返回**-1**。
为了使代码更短,我使用了ternary-operator,但如果你愿意,你可以用if-else来写它!
字符串
gj3fmq9x8#
字符串