美文网首页初识算法
字符串中的第一个唯一字符

字符串中的第一个唯一字符

作者: 无名指666 | 来源:发表于2019-08-05 18:15 被阅读0次

    给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
    案例:
    s = "leetcode"
    返回 0.
    s = "loveleetcode",
    返回 2
    注意事项:您可以假定该字符串只包含小写字母。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题思路:

    我们要查找第一个唯一的字符串,怎么才叫唯一呢,只出现一次,那我们就可以找如果出现两次会发生变化的相关解法

    一、使用map,遍历一遍将其本身和索引下标存储,然后再遍历一遍字符串,看在map里存储的本身的索引和现在一致么,一致表示是第一个唯一存在,返回;

    //判断字符串中的第一个唯一字符---map
        class Solution {
            public int firstUniqChar(String s) {
                Map<Character,Integer> map=new HashMap<Character,Integer>();
                for (int i = 0; i < s.length(); i++) {
                    map.put(s.charAt(i),i);
                }
                for (int i = 0; i < s.length(); i++){
                    if(map.get(s.charAt(i))== s.indexOf(s.charAt(i))){//说明是唯一的                        return i;
                    }
                }
                return -1;
            }
        }
    

    空间复杂度:O(n),
    时间复杂度:O(n);

    解法二: 使用string本身特性,判断字符的indexof()和lastIndexof();是否相等,相等说明一致;

    //判断字符串中的第一个唯一字符---indexof()
    class Solution {
           public int firstUniqChar(String s) {
               for (int i = 0; i < s.length(); i++) {
                   char re=s.charAt(i);
                   if (s.indexOf(re)== s.lastIndexOf(re)){
                       return i;
                   }
               }
               return -1;
           }
       }
    

    时间复杂度:O(n);
    空间复杂度:O(1);

    解法二优化:只遍历26个小写字母,当字符串超长时,减少循环次数

    class Solution {
            public int firstUniqChar(String s) {
                int index=-1;
                for (char ch = 'a'; ch <= 'z'; ch++) {//只遍历26哥字母
                    int beginindex=s.indexOf(ch);
                    if (beginindex != -1 && beginindex==s.lastIndexOf(ch)){
                        index=(index == -1 || index>beginindex) ? beginindex :index;
                    }
                }
                return index;
    
            }
        }
    

    每天一算法,成功有方法。坚持
    原文链接:

    https://leetcode-cn.com/problems/first-unique-character-in-a-string/

    相关文章

      网友评论

        本文标题:字符串中的第一个唯一字符

        本文链接:https://www.haomeiwen.com/subject/lqzmdctx.html