0

「Unicode 文字のリンク リストで繰り返し要素を見つけます。Unicode 文字に重複が見つかった場合は、その繰り返しノードを削除してリストを調整します。制約は、余分なメモリを使用しないことでした。」</p>

私の答え:
Unicode char にサロゲート ペア char が含まれていないと仮定すると、C# を使用しているため

リストをたどる際に前のノードの値を知っていない限り、重複する文字を見つける方法がわかりません。以前の値を維持するには、追加のメモリ (ハッシュ テーブル) が必要になります。

皆さん、この質問に対する解決策を思いつくことができますか? あるサイトでのインタビューの質問です。また、これを O(n) 時間で解決することは可能ですか?
これが私の実装です。より良いものにするために、フィードバックをいただけますか?

public static void RemoveDup(Node head)
        {
            Node current1 = head;
            Node current2;



            while (current1 != null)
            {
                current2 = current1;
                while (current2 != null)
                {
                    if (current2.Next!=null && current1.Data == current2.Next.Data)
                    {
                        Node temp = current2.Next.Next;
                        current2.Next = temp;
                        current2=current1;
                        continue;                        
                    }

                    current2 = current2.Next;
                    if (current2 == null)
                        break;

                }

                current1 = current1.Next;
                if (current1 == null)
                    break;
            }


        }
4

3 に答える 3

2

リスト内の各要素について、その要素のリストを検索し、要素がなくなるまで、その要素の位置から削除します。

実装とその他の選択はあなたにお任せします。

于 2009-07-24T14:28:02.267 に答える
0

リストを並べ替える - すべての重複が一列に並んでいます。それには O(nlogn) 時間がかかります。もちろん、リストを並べ替えることができ (おそらく順序が重要ですか?)、その場で並べ替えることができる (余分なメモリは必要ありません) ことを前提としています。

于 2009-07-24T17:26:27.487 に答える
0

以前に見た値を何らかの形で保存せずにこれを行う唯一の方法は、ネストされたループを使用することです。外側のループは「リスト全体をトラバースする」、内側のループは「リスト全体をトラバースし、外側のループが指すアイテムのコピーを削除する」です。

于 2009-07-24T14:29:46.133 に答える