7

実際、これは数日前のインタビューの質問です。

ArrayListインタビュアーは、との違いを表現してほしいと言いLinkedList、 での挿入操作を最適化する、ArrayListつまり再実装するように求めました。add(int index, E element)もちろん操作の複雑さはget(int index)犠牲にできます。

私の答えは、配列を k 個のサブ配列に分割し、対応するサブ配列に既に含まれている要素の数を表すカウント配列を更新することでした。また、すべてのサブ配列のメモリは、予想される初期サイズで動的に割り当てられます。にデータを挿入する必要がある場合はArrayList、最初にサブ配列を見つけて、小さな配列内で操作を実行できます。また、挿入があまり頻繁でない場合、またはインデックスが均一に分散されている場合、挿入の時間の複雑さはO(log(k) + n/k + k)平均的である可能性があります。log(k)つまり、カウント配列の合計配列でバイナリ検索を使用して最初にサブ配列を見つける必要があることを意味し、n/kデータ移動またはメモリの再割り当て、k は合計配列の更新を表します。

より良い解決策があると確信しています。いくつかの提案が必要です、ありがとう！

4

4 に答える 4

0

add() と get() の両方のコストが O(logn) になるように、バランスの取れたバイナリ ツリーで実装できます。

実装例は次のようになります (ここでは手作りで、コンパイルされず、コーナー ケースはカバーされていません)。

class Node {
  int subTreeSize;
  Node left,right;
  Element e;
  // all i 0-indexed
  Node get(int i) {
    if (i >= subTreeSize) {
      return null;
    }
    if (left != null) {
      if(left.subTreeSize > i) {
        return left.get(i);
      } else {
        i -= left.subTreeSize;
      }
    }
    if (i == 0) {
      return this;
    }
    return right.get(i-1);
  }

  // add e to the last of the subtree
  void append(Element e) {
    if(right == null){
      right = new Node(e);
    } else {
      right.append(e);
      right = right.balance();
    }
    subTreeSize += 1;
  }

  // add e to i-th position
  void add(int i, Element e) {
    if (left != null) {
      if(left.subTreeSize > i) {
        add(i,left);
        left=left.balance();
      } else {
        i -= left.subTreeSize;
      }
    }
    if (i == 0) {
      if (left == null){
        left = new Node(e);
      } else {
        left.append(e);
        left = left.balance();
      }
    } else {
      if (right  == null) {
        // also in this case i == 1
        right = new Node(e);
      } else {
        right.add(i-1, e);
        right = right.balance();
      }
    }
    subTreeSize += 1;
  }
  // the common balance operation used in balance tree like AVL or RB
  // usually just left or right rotation
  Node balance() {
    ...
  }
}

public class Tree {
  Node root;
  public Element get(int i) {
    return root.get(i).e;
  }
  public void add(int i, Element e) {
    if (root == null) {
      root = new Node(e);
    } else {
      root.add(i,e);
      root = root.balance();
    }
  }
}
于 2014-11-27T02:54:01.537 に答える
-1

LinkedList は、access\insert\remove が O(n) を必要とするリンク リストです。リンク リストは、シーケンシャル アクセス O(n) をサポートします。

ArrayList は挿入\削除の配列で、O(2n) が必要ですが、アクセスには O(1) が必要です。配列はランダム アクセス O(1) をサポートします。

より最適なハイブリッド構造を見つけるには、次から始めることができます。

template <T>
public class LinkedArrayList
{
    LinkedList<ArrayList<T>> list;

    public LinkedArrayList ()
    {
        list = new LinkedList<ArrayList<T>> ();
    }

    // ..
}

アクセスの複雑さと、複雑さの挿入と削除の間で、リスト内のセグメント (配列) のバランスを取る必要があります。

于 2013-04-06T09:21:41.470 に答える