剑指offer—字符串中只出现一次的第一个字符 解答

剑指offer—字符串中只出现一次的第一个字符

题目描述

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

思路

使用hash表存储每个字符对应出现的次数,从前往后遍历,如果获取到字符的次数为1,直接输出

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

代码

  • 遍历所有字符串内字符
public class Solution {
    public int FirstNotRepeatingChar(String s) {
        Map<Character,Integer> map = new HashMap();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(map.get(c)!=null){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
         for(int n=0;n<s.length();n++){
             if(map.get(s.charAt(n))==1) return n;
         }
        return -1;
    }
}
  • 只遍历map中有的字符,即不重复出现的字符

它这里只能使用需要使用LinkedHashMap来通过链表保证插入的顺序,TreeMap只能保证key的排序(字符就是字母表,数字就是大小),HashMap而不进行排序,LinkedHashMap迭代比HashMap快

class Solution {
    public int firstUniqChar(String s) {
        Map<Character,Integer> map = new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(map.get(c)!=null){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
         for (Map.Entry<Character, Integer> entry : map.entrySet()) {
             if(entry.getValue()==1) {
                 return s.indexOf(entry.getKey());
             }
         }
        return -1;
    }
}