LeetCode中字符串中的第一个唯一字符题解

LeetCode 算法

LeetCode

发布日期: 2020-12-09

文章字数: 535

阅读时长: 2 分

阅读次数:

LeetCode字符串中的第一个唯一字符题解-java

题目

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

难度简单296

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

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示：你可以假定该字符串只包含小写字母。

题解

方法一：哈希表存放字符及其出现次数

思路

遍历一遍字符串，然后将字符串中每个字符及其相应出现的次数存放在一个哈希表中，然后遍历这个字符串，判断在哈希表中出现的次数，若找到第一个出现次数为1时，则返回此时下标

代码实现

class Solution {
    public int firstUniqChar(String s) {
        // 新建一个hashmap散列表用来存放出现的字符及其相应出现的次数
        HashMap<Character,Integer> hashmap = new HashMap<>();
        // 遍历字符串，存放字符及其相应出现的次数
        for(int i = 0; i < s.length(); i++){
            if(!hashmap.containsKey(s.charAt(i))){
                hashmap.put(s.charAt(i), 1);
            }else{
                hashmap.put(s.charAt(i), hashmap.get(s.charAt(i)) + 1);
            }
        }
        // 遍历字符串，遇到第一个字符出现的次数为1时，返回此下标
        for(int j = 0; j < s.length(); j++){
            if(hashmap.get(s.charAt(j)) == 1){
                return j;
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度： O(N)只遍历了两遍字符串，同时散列表中查找操作是常数时间复杂度的。

空间复杂度： O(N)用到了散列表来存储字符串中每个元素出现的次数。

提交详情

方法二：

思路

使用一个长度为26的int数组来存放字符出现的次数，数组的下标即对应26个字母

代码实现

class Solution {
    public int firstUniqChar(String s) {
        int[] chars = new int[26];
        for (char c : s.toCharArray()) {
            chars[c - 'a'] += 1;
        }
        for (int i = 0; i < s.length(); ++i) {
            if (chars[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}