P132 第一个只出现一次的字符

描述#

这个题目说的是，给你一个只包含小写字母的字符串，你要找到第一个只出现一次的字符，并返回它的下标。如果字符串中所有字符都不只出现一次，则返回 -1。

比如说，给你的字符串是：
apple
第一个只出现一次的字符是 a，于是你要返回它的下标 0。
如果给你的字符串是：
noon
这个字符串中的两个字符 o 和 n 都不只出现一次，因此返回 -1。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(m)
  public int firstUniqCharTwoPass(String s) {
    if (s == null || s.length() == 0) return -1;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); ++i)
      ++count[s.charAt(i) - 'a'];
    for (int i = 0; i < s.length(); ++i)
      if (count[s.charAt(i) - 'a'] == 1)
        return i;
    return -1;
  }

  // Time: O(n), Space: O(m)
  public int firstUniqCharOnePass(String s) {
    if (s == null || s.length() == 0) return -1;
    int[] count = new int[26];
    int[] pos = new int[26];
    Arrays.fill(pos, -1);
    for (int i = 0; i < s.length(); ++i) {
      int idx = s.charAt(i) - 'a';
      ++count[idx];
      if (pos[idx] == -1) pos[idx] = i;
    }
    int firstPos = Integer.MAX_VALUE;
    for (int i = 0; i < 26; ++i)
      if (count[i] == 1)
        firstPos = Math.min(firstPos, pos[i]);
    return firstPos == Integer.MAX_VALUE ? -1 : firstPos;
  }

}