8

これは Google のインタビュー パズルでした。

問題は、一度だけ出現する配列内の最初の要素を見つけることです。

たとえば、abaaacdgadgfが与えられます。を出力する必要がありますb。

簡単な解決策は、最初にハッシュテーブルを使用してすべての要素をカウントし、次にもう一度ループして最初の要素を取得することです。2 ループを使用します。

1 ループだけで結果を取得することは可能ですか?

私はそれを理解しようとしましたが、それは不可能のようです。

4

5 に答える 5

2

ここに私の解決策：

各「文字」には、可能な 4 つの統計情報があります。

  • 1 : 見たことがない。
  • 2 : 見たもの
  • 3 : 複数出現のため除外。
  • 4 : 資格あり

文字の統計を格納するために、サイズ 26 (各「文字」) の配列を作成します。修飾された要素は、デュアル リンク リストの最後に配置されます。

入力データをスキャンし、必要に応じてすべての更新を行います。次に、リストを最初から最後までスキャンします。最初の「除去されていない (状態 3)」があなたの答えです。

complexity : n+(26x3) where n = length(dataset)
于 2013-07-09T09:03:24.317 に答える
1

自分で試してみたいという理由だけで、他の回答を読んでいません。
解決策を繰り返し改善しましょう。時間と空間
の複雑さに関する分析では、最初にいくつかのことを明確に述べる必要があります。 

N = length of string 
M = numbers of characters in alphabet

ブルート フォース アルゴリズムは、文字列をトラバースし、文字列の各要素について、その右側を検索して重複があるかどうかを確認することです。
時間の複雑さ:O(N 2 )
空間の複雑さ:O(1)

もっとうまくやれるでしょうか？
確かに、文字列をトラバースして、文字が出現する回数を数えることができます。文字列をもう一度トラバースして、カウント 1 を持つ最初の文字を見つけます。
時間の複雑さ:O(N+M)
空間の複雑さ:O(M)

なぜこれは O(N+M) なのですか?
最初に count 配列の要素を 0 に初期化する必要があるためです。したがって、入力が "a" であっても、M 個の要素の count 配列を初期化する必要があります。

もっとうまくやれるでしょうか？
最初に、このタスクが Omega(N) であることをインタビュアーに伝えましょう。これは、文字列の各要素を少なくとも 1 回確認する必要があるためです。「aaaaaaz」の入力インスタンスを確認することでこれを実現します。
したがって、時間の複雑さを改善することを目的としていません。文字列を 1 回トラバーサルするだけで、実際の実行時間を短縮できます。
これは確かに可能です。

for(int i=0;i<N;i++)
{
  if(visited[i]==-2)continue;
  if(visited[i]==-1)visited[i]=i;continue;
  visited[i]=-1;
}
int F=N;
char res=' ';
for(int i=0;i<M;i++)
{
  if(visited[i]>=0)
  {
    F=min(F,visited[i]);
    res=A[visited[i]];
  }
}
return res;

時間の複雑さ:O(N+M)
空間の複雑さ:O(M)

もっとうまくやれるでしょうか？

おそらくO（N）でこれを行うことはできますか？
私はまだ真のO（N）でこれを行う方法を考えています。解決策を見つけたら、この回答を更新します。

于 2013-07-09T12:13:48.367 に答える
1

ハッシュ テーブルの代わりに、トライを使用できます。入力データがハッシュ関数に対して共謀する場合、ハッシュテーブルは 2 次のパフォーマンスを実現します。トライはその影響を受けません。

別のループについては、あまり気にしません。漸近的には同じ複雑さです。ループを排除することで得られるものは何であれ、残りのコードの複雑さが増して失われる可能性があります。

于 2013-07-09T12:57:04.610 に答える