https://leetcode.com/problems/insert-delete-getrandom-o1/

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Random 한 수를 얻을 수 있는 class를 만들어 달랜다.

umap으로 들어오는 값을 pair<arg값, arg가 vector에 저장될 idx> 로 저장해준다.

class RandomizedSet {
	std::unordered_map<int, int> umap;  // pair<val, idx>
	std::vector<int> randomV;

	int vIndx;
public:
	/** Initialize your data structure here. */
	RandomizedSet() {
		vIndx = 0;
	}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
	bool insert(int val) {
		if (umap.find(val) != umap.end())
			return false;
		else
		{
			umap[val] = vIndx;
			randomV.push_back(val); // vector에 값을 저장.
			vIndx++;
			return true;
		}
	}

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	bool remove(int val) {
		if (umap.find(val) != umap.end())
		{
			int idx = umap[val];
			if (idx == randomV.size() - 1) // vector.size가 하나 이거나 끝에서 뺄때는 복잡할거 없이 끝에서만 빼주면된다.
			{
				randomV.pop_back();
				umap.erase(val);
				vIndx--;
				return true;
			} // 그렇지 않다면 vector 어딘가에서 값을 빼야하는데 이때 빼고 땡겨주는 것이 아닌 끝에 있는 값을
				// 넣어준다. 그리고 끝은 pop 시켜주면 된다. umap에서 idx를 관리하니까 여기도 update 시켜준다.
			int lastVal = randomV.back();
			randomV[idx] = lastVal;
			randomV.pop_back();
			umap[lastVal] = idx; // map에서 val로 저장했던 idx 값도 update 해줘야 한다.
			vIndx--;
			umap.erase(val);
			return true;
		}
		else
			return false;
	}

	/** Get a random element from the set. */
int getRandom() {
		return randomV[rand() % randomV.size()];
	}
};

Runtime: 36 ms, faster than 93.82% of C++ online submissions for Insert Delete GetRandom O(1).

Memory Usage: 22.6 MB, less than 65.51% of C++ online submissions for Insert Delete GetRandom O(1).

이것도 써봤는데 엄청 느리다.

/** Get a random element from the set. */
	int getRandom() {
		std::random_device rd;
		std::mt19937 mt(rd());
		std::uniform_int_distribution<int> dist(0, randomV.size() - 1);
		int rand = dist(mt);

		return randomV[rand];
		//return randomV[rand() % randomV.size()];
	}