2

これは面接の質問です。指定された文字列の最初の文字を見つけます。これは1回だけ表示されます（ソリューションはJavaである必要があると思います）。

例えば：

"babcbcd"->'a' //'a'と'd'の両方が1回だけ表示されますが、'a'は'd'の前に表示されます

簡単な解決策は

  • マップを作成します（例HashMap）：char->文字列内の出現数。
  • 文字列をスキャンし、文字の値が1になるまで、マップに対して文字列文字をテストします。

それは意味がありますか？最良のマップ実装は何ですか？より良い、より効率的な解決策はありますか？

4

8 に答える 8

3

LinkedHashMap<Character,Integer>Javaでは、aを使用して、各文字が文字列に出現する回数をカウントできます。挿入順序が保持されるためLinkedHashMap、エントリを繰り返し処理して、1回だけ表示される最初の文字を見つけることができます。

合理的な仮定の下で、これは解決策を与えるでしょうO(n)。

于 2013-02-17T15:10:48.737 に答える
3

これがHaskellのバージョンです。

import Data.List (elemIndices)
firstSingle str = take 1 [a | a <- str, length (elemIndices a str) == 1]

*メインData.List>firstSingle"babcbcd"
"a"

于 2013-02-17T20:14:55.900 に答える
2

私がインタビューをしているとしたら、私は次のようなことを望んでいます（必ずしも期待しているわけではありませんが）。

def string = 'babcbcd'
def singles = string.toList().groupBy{ it }.findAll{ it.value.size() == 1 }.collect{ it.key }
println "First char that appears once: " + string.find{ singles.contains it }

重要なのは真ん中の線です。文字列を文字のリストとして受け取り、リストを文字ごとにグループ化して、一度だけ発生しなかったものをすべて除外し、最後に一度発生した文字のリストを生成します。次に、そのリストにある最初の文字を文字列で検索します。

Javaでこれほどエレガントになることは不可能なので、Groovyです。たぶん、JDK8がついにそれを作ったら...

更新：@groovyのHaskellソリューションに触発されたより簡潔なバージョン。私は今、私の最初のものの不器用さにほとんど当惑しています:)

def firstUnique(seq) { seq.findAll{ seq.count(it) == 1 }.first() }
于 2013-02-17T17:04:16.037 に答える
1

元の文字列の1つのパスでそれを行うことができます。リンクされたハッシュマップを作成し、これまでに見つけた文字の数を保存します。次に、マップエントリを確認し（リンクされたマップであるため、挿入順になります）、1のカウントが表示されたら停止します。

于 2013-02-17T15:13:12.793 に答える
1

あなたはすでに良い解決策を見つけました、しかしあなたが望むなら私は別のアプローチを提案します：

final String abc = "abcdefg....z";
boolean scanned[] = new boolean[abc.lenght()];
//set all to false ...
for(int i = 0; i<yourString.lenght(); i++){
    char c = yourString.charAt(i);
    if(!scanned[abc.indexOf(c)]){
        for(int j=i+1; j<yourString.lenght(); j++)
            if(yourString.charAt(i) == c){ // founded another
                scanned[abc.indexOf(c)] = true;
                break;
            }
        if(!scanned[abc.indexOf(c)])
            return c;
    }
}
于 2013-02-17T15:37:38.717 に答える
1

上記のすべてのソリューションにはO（n）メモリが必要です.O（1）メモリでそれを行うには、すべての文字に対してforループを実行し（ASCIIでは128あります）、出現数と最初の出現数をカウントしてから、最初の繰り返されない文字を見つけます。時間計算量O（128 | s |）。

int min=Integer.MAX_VALUE;
char ans=' '; //any initialization 
for ( i=0; i<128;i++){
    int count=0,first=-1;
    for(j=0;j<s.length();j++){
         if(s.charAt(j)==(char)(i)) count++;
         if(count==1) first=j;
         if(count>1) break;
    }
    if(count==1 && min>first){
         first=min;ans=s.charAt(first);
    }
}
if(min!=Integer.MAX_VALUE) System.out.println(ans);
else System.out.println("No such char found");
于 2013-02-17T15:59:59.333 に答える
1

がaz文字のみで構成されていると仮定すると、Stringこれまでに表示された文字のキューを使用して、カウントを続けることができます。

public static String findFirstLetterThatAppearsOnceInString(String str) {
    int[] seenCount = new int[26];
    int[] queue = new int[26];
    int queueSize = 0;
    for (char c : str.toCharArray()) { // Iterate over the input characters
        int i = c-'a';
        if (seenCount[i]<2) {
            seenCount[i]++;
            // If seen for the first time, store it in queue
            if (seenCount[i]==1) queue[queueSize++]=i;
        }
    }
    for (int qi=0;qi<queueSize;qi++) if (seenCount[queue[qi]]==1) return (char)(queue[qi]+'a')+"";
    return null;
}
于 2013-02-17T16:27:28.000 に答える
1

ユニコードがないと仮定した、単純な非マップソリューション：

public String firstLonelyChar(String input)
{
    while(input.length() > 0)
    {
        int curLength = input.length();
        String first = String.valueOf(input.charAt(0));
        input = input.replaceAll(first, "");
        if(input.length() == curLength - 1)
            return first;
    }
    return null;
}
于 2013-02-17T20:54:56.447 に答える