leetcode 387 First Unique Character in a String

lc387 First Unique Character in a String

两种思路

1）统计各个字母出现的次数，然后再遍历一次原数组，输出只出现一次元素的index

可以用hashmap统计次数，也可以申请一个大小为26的int数组

 1 class Solution {
 2     public int firstUniqChar(String s) {
 3         int abc[] = new int[26];
 4         
 5         for(int i=0; i<s.length(); i++){
 6             abc[s.charAt(i)-'a']++;
 7         }
 8         
 9         for(int i=0; i<s.length(); i++){
10             if(abc[s.charAt(i)-'a'] == 1)
11                 return i;
12         }
13         
14         return -1;
15     }
16 }

2）双指针

一个快指针，向后遍历统计字母出现次数，一个慢指针，指向当前只出现一次且index最小的元素

 1 class Solution {
 2     public int firstUniqChar(String s) {
 3         if(s==null || s.length()==0) return -1;
 4         int slow=0,fast=0;
 5         char[] chs=s.toCharArray();
 6         int[] count=new int[256];
 7         int n=chs.length;
 8         while (fast<n){
 9             count[chs[fast]]++;
10             while (slow<n && count[chs[slow]]>1){
11                 slow++;
12             }
13             if (slow==n) return -1;
14             fast++;
15         }
16         return slow;
17     }
18 }

3）巧用indexOf()&lastIndexOf()

一个minIdx记录答案

与前两者统计字母出现次数不同，这个方法不遍历数组，而是遍历26个小写字母

indexOf()求当前字母第一次出现的位置，lastIndexOf()求最后一次出现的位置，比较这两者

若存在，且两者相等就说明只出现过一次

 1 public class Solution {
 2     public int firstUniqChar(String s) {
 3         if(s.length() == 0)
 4             return -1;
 5         
 6         int minIdx = s.length();
 7         
 8         for(char i = 'a'; i<='z'; i++){
 9             int fp = s.indexOf(i);
10             int lp = s.lastIndexOf(i);
11             if(fp != -1 && fp == lp)
12                 minIdx = Math.min(minIdx, fp);
13         }
14         
15         return minIdx == s.length() ? -1 : minIdx;
16     }
17 }