解答と解説: Insert, delete, contains and getRandom with O(1)（重複許容版）

「問題演習: Insert, delete, contains and getRandom with O(1)（重複許容版）」の解答編です。今回の解答は前回の重複を許容しない場合の解答と似ているので、解法の大枠はそちらをご覧ください。今回の解説では重複を許容する際に注意すべき点を挙げます。

解答例

Javaでの解答例です。

	public class Solution {
	private List<Integer> list;
	private Map<Integer, Set<Integer>> map; // key=n, value=set of indices
	private Random random = new Random();
	public Solution() {
	list = new ArrayList<>();
	map = new HashMap<>();
	}
	public boolean insert(int val) {
	boolean contains = map.containsKey(val);
	if (!contains) {
	map.put(val, new HashSet<>());
	}
	map.get(val).add(list.size());
	list.add(val);
	return !contains;
	}
	public boolean delete(int val) {
	if (!map.containsKey(val)) {
	return false;
	}
	Set<Integer> indices = map.get(val);
	int index = indices.iterator().next();
	indices.remove(index);
	if (indices.isEmpty()) {
	map.remove(val);
	}
	if (index < list.size() - 1) {
	int lastVal = list.get(list.size() - 1);
	list.set(index, lastVal);
	map.get(lastVal).remove(list.size() - 1);
	map.get(lastVal).add(index);
	}
	list.remove(list.size() - 1);
	return true;
	}
	public boolean contains(int n) {
	return map.containsKey(n);
	}
	public int getRandom() {
	int n = random.nextInt(list.size());
	return list.get(n);
	}
	}

view raw answer-insert-delete-contains-and-getrandom-with-o1.java hosted with ❤ by GitHub

解説

重複を許容しない場合との違いは、マップの値がセットであることに加え、insert と delete の実装が変わったことです。contains と getRandom の実装は変わりません。

マップのキーには insert の引数として与えられた整数 n を用い、値にはリスト上でのインデックスが複数格納できるようにセットを値としています。ここでセットを用いているのは、値の入手した順序を記憶しておく必要がないためです。

insert の実装は特に難しいところはありません。重複を許すので、どのような値に対しても追加するだけです。delete ではマップの値であるセットが空になった場合、引数である整数 n は全て削除されたということなので、マップから整数 n のエントリーを削除します。

以上が解説です。前回の重複を許容しない場合を自力で解くことができていれば、今回の問題は簡単に解くことができたと思います。解き方をすぐに思いつくことができるように、繰り返し挑戦しましょう。

---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。