Leetcode-387-字符串中的第一个唯一字符

Leecode-387-字符串中的第一个唯一字符

思路：哈希表

题目描述

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

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

思路：哈希表

• 第一次遍历：遍历一遍字符串，把所有的字符串及对应的出现次数存入哈希表中。
• 第二次遍历：遍历一遍字符串，去哈希表中检查出现次数为1的字符在不在哈希表中，并且返回它的索引。

举例

1. 存入哈希表

2. 返回对应第一次出现次数为1的索引

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> map = new HashMap<>();

        // 1. 遍历存入哈希表
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),map.get(s.charAt(i)) + 1);
            }else {
                map.put(s.charAt(i),1);
            }
        }
        // 2. 如果只出现一次 就返回
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1){
                return i;
            }
        }
        // 3. 否则不存在
        return -1;
    }
}

class Solution {
    public int firstUniqChar(String s) {
        int[] frequency = new int[26];
        int len = s.length();

        // 1. 遍历存入数组
        for(int i = 0;i < len;i++){
            frequency[s.charAt(i) - 'a']++;
        }

        // 2. 返回只出现一次的元素
        for(int i = 0;i < len;i++){
            if(frequency[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }

        // 3. 否则返回-1
        return -1;
    }
}

复杂度分析：

• 时间复杂度：O(n) 遍历两次的时间复杂度
• 空间复杂度：O(n) 哈希表的额外空间

打赏