java - 算法：在输入字符串中查找第一个不重复的字符

Question

我已经看到了这个和这个问题，但我的不同。我想用java为它写一个有效的代码。我想出了2个解决方案：

方法 1。

find_first_reapeted(char[] input)
{
    HashMap<Character,Integer> myhash = new HashMap<Character,Integer> ();
    for(int i=0;i<input.length;i++)
    {
      if(myhash.containsKey(input[i])
          myhash.put(input[i],2); //just put 2 even if it is more than 2
      else
          myhash.put(input[i],1);
    }
    for(int i=0;i<input.length;i++)
    {
      if(myhash.getValue(input[i])==1)
         return input[i];
    }
}

方法 2。

find_first_reapeted(char[] input)
{
    int[] allchars = new int[26];
    for(int i=0;i<input.length;i++)
    {
        allchars[input[i]-'a'] += 1;
    }
    for(int i=0;i<input.length;i++)
    {
      if(allchars[input[i]-'a']==1)
         return input[i];
    }
}

首先有没有更好的解决方案？（时间和空间复杂度的术语）？如果不是以上哪一项更好？我不确定hashmap的空间复杂度！

Answer 1

怎么样

第一个重复字符。

char find_first_repeated(char[] input) {
    BitSet bs = new BitSet();
    for(char c : input) {
        if(bs.get(c))
           return c;
        bs.set(c);
    }
    return '\uffff'; // invalid char
}

第一个非重复字符，我将使用第二种方法，但使用 for-each 循环使其更清晰。