0

キャリアカップでこの質問を読みましたが、「SkipList」以外に良い答えが見つかりませんでした. ウィキペディアで見つけたSkipListの説明は興味深いものでしたが、「幾何/二項分布」などの用語がわかりませんでした...それが何であるかを読んで、確率論に深く入り込みました。単純に、検索を高速化する方法を実装したかっただけです。1. インデックスを作成しました。- たとえば 1000 個のノードを作成する関数を作成しました。次に、連結リスト型の配列を作成し、1000 個のノードをループして、23 番目ごとの要素 (頭に浮かんだ乱数) を選択し、「インデックス」と呼ぶ配列に追加しました。

    SLL index = new SLL[50]

次に、インデックスを作成する関数:

    private static void createIndex(SLL[] index, SLL head){
    int count=0;
    SLL temp = head;
    while(temp!=null)
    {
        count++;
        temp = temp.next;
        if((count==23){
            index[i] = temp;
            i++;
            count=0;
        }
    }       
}

最後に「検索」機能です。その関数では、最初に入力要素 769 を例に取ります。「index」配列を調べると、index[i]>769 が見つかります。したがって、head = index[i-1] と tail = index[i] を「find」関数に渡します。次に、23 要素の短い範囲で 769 を検索します。したがって、必要な要素を見つけるのに合計 43 回のジャンプ (配列ジャンプと node=node.next ジャンプを含む) が必要であると計算しました。 769回ジャンプしました。

注: インデックス配列を作成するコードは検索の一部ではないと考えているため、'find' 関数の時間の複雑さに時間の複雑さ (ひどい) を追加しません。このインデックスの作成は、リストが作成された後に別の関数として行うか、またはタイムリーに行う必要があると思います。ウェブページが Google 検索で表示されるまでに時間がかかるのと同じです。また、この質問は Microsoft のインタビューで聞かれましたが、私が提供したソリューションは役に立つものなのか、それともそのような種類のソリューションを提供することで馬鹿に見えるのでしょうか。ソリューションは Java で記述されています。あなたのフィードバックを待っています。

4

1 に答える 1

1

ここで解決しようとしている問題が何であるか、または解決策がどのように機能するかを理解するのは困難です。(ヒント: 完全に機能するコードは両方に役立ちます!)

ただし、一般的に言えることはいくつかあります。

  • ある種の順序付けが行われていない限り、リストのデータ構造を検索することはできません (たとえば、リスト内で検索するなどi) 。O(N)たとえば、要素の並べ替え。

  • リストの要素がソートされていて、リストがインデックス可能である場合 (つまり、位置の要素を取得するi場合O(1))、二分探索を使用して 内の要素を見つけることができますO(logN)。

  • i連結リストの位置にある要素をより良い方法で取得することはできませんO(N)。

セカンダリ データ (インデックスなど) を追加すると、特定の操作のパフォーマンスが向上する可能性がありますが、ストレージ スペースが増え、他の特定の操作のコストが高くなります。ただし、リスト/リンクされたリストはもうありません。データ構造全体は「別のもの」です。

于 2015-11-01T02:04:28.567 に答える