LeetCode387-First Unique Character in a String

题目

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Example:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note:

You may assume the string contain only lowercase letters.

分析

解法一:标记重复元素

利用一个与输入字符串等长的boolean数组isRepeat标记元素是否重复,实现上采用双重循环,逐个访问每个元素,先看isRepeat[i]是否已标为重复true,若是则跳过它,否则进一步在二层循环中又逐个访问其之后的所有元素,若与自身相同,标记为true。直到访问到某个元素与它之后的所有元素都不重复,返回。

解法二:统计重复频次

更妙的方式是开辟一个字母表数组,逐个遍历输入单词的字母,统计其对应位置上的次数。最后又根据输入单词的顺序,再度遍历,第一个频次为1的元素就是所求。

代码

解法一

public class Solution {
    public int firstUniqChar(String s) {
        if(s.length() == 1) 
            return 0;
        
        boolean[] isRepeat = new boolean[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            
            if(isRepeat[i] == false) {
                //未重复
                char ch = s.charAt(i);
                int j;
                boolean hasRepeated = false;
                for (j = i + 1; j < s.length(); j++) {
                    if (ch == s.charAt(j)) {
                        isRepeat[j] = true; //标记为重复元素
                        hasRepeated = true;
                    }
                }
                if (hasRepeated == false) //证明未检测到重复
                    return i;
            }
        }
        
        return -1;
    }
}

解法二

public class Solution {
    public int firstUniqChar(String s) {
        
        //统计字母出现频次
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++)
            freq[s.charAt(i) - 'a']++;
        
        //按s的顺序找出只出现1次的元素
        for (int i = 0; i < s.length(); i++) 
            if (freq[s.charAt(i) - 'a'] == 1)
                return i;
        
        return -1;
    }
}

Leave a Comment.