set（）メソッドとO（1）を含むJavaデータ構造体Contains（）

特定のインデックスの項目を置き換えることができる順序付けされたデータ構造がJavaで存在し、O（1）？set（）メソッドとO（1）を含むJavaデータ構造体Contains（）

LinkedHashSetはほとんど私が探しているものですが、インデックスを使用してアイテムを設定/置換することはできません。

2016-12-13 Jimmy P

が含まれ、そのように、あなたが扱うことができる

map.computeIfPresent(object, (k, v) -> v > 1 ? v - 1 : null);

が、彼らはあまりにも高Aました：要素を削除しますコスト。だから私は問題を回避するだけで2つの方法を持って小さなインターフェイスを作成して作業しました。 "解決策にあればセットする"、 "解決策にする"クラス自体では、それらのためにローカル変数を使用しなければなりませんでした。最もエレガントではありませんが、うーん、それは動作します。また、ソートされたリストに含まれるものは、バイナリ検索を行うことができるので、複雑さのログ（n）になる可能性があります。 2〜3本の木を使うことができると考えれば、さらに低くなります。要素をチェックするのに、低コストでソートされますが、インデックスの置き換えはありません：/ – MrKickkiller

O（1）でも削除できるようにしたいですか？ – vaxquis

@vaxquisいいですが、重要ではありません。 –

あなたはArrayList内の項目を保存使用して、リストを使用して要素にList許可するアクセスにおける等価クラスの要素数と要素の型からマッピングするためにHashMap<ItemType, Integer>を使用している場合、あなたがテストすることができますすることができますアイテムは、要素を追加するためのマップを更新

Integer i = map.get(object); 
boolean contained = (i != null) && (i > 0);

を使用して含まれている：

map.merge(object, 1, Integer::sum);

項目がリストに置き換えられた場合、私はまた、で動作するように持っていたの割り当てについては

map.merge(newValue, 1, Integer::sum); 
map.computeIfPresent(oldValue, (k, v) -> v > 1 ? v - 1 : null);

出典

2016-12-13 23:45:04 fabian

標準Javaクラスには含まれていません。あなたはHashSetとArrayListを構成するクラスをかなり簡単に作ることができます。

出典

2016-12-13 23:36:58

2倍のメモリコスト。 – shmosel

真。しかし、それはLinkedHashSetよりも悪くありません。 –

@shmoselメモリコストの2倍ではありません。余分なコストは、要素のサイズに亘って償却されます。それらがIntegersであれば、それは比較的高価になります。それらがそれぞれ1000バイトの場合、追加コストはごくわずかです。 –

set（）メソッドとO（1）を含むJavaデータ構造体Contains（）

答えて

関連する問題