0

私はこれとこの質問を見てきましたが、私のものは異なります。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];
    }
}

まず、より良い解決策はありますか？(時間と空間の複雑さの項)? そうでない場合、上記のどれが優れていますか？ハッシュマップのスペースの複雑さについてはよくわかりません!

4

1 に答える 1

3

どうですか

最初の繰り返し文字。

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
}

最初の繰り返しのない文字。私は 2 番目のアプローチを使用しますが、for-each ループを使用してよりクリーンにします。

于 2013-10-03T20:38:25.963 に答える