Мне сегодня задали следующий вопрос: Может ли кто-нибудь поделиться O (n) решением (с постоянным пробелом) следующей проблемы, если это возможно?
/ ******************************************************************************
Завершите следующую функцию, которая принимает вектор целых чисел в качестве аргумента и удаляет повторяющиеся значения, так что не более двух экземпляров одного и того жезначение остается в векторе. Порядок оставшихся элементов должен быть сохранен.
Например, с учетом следующего ввода: 0, 10, 10, 100, -1, -1, -1, 5, 5, 5, 8, 9,10, 10, 3, 9, 7, 0, 0, 0
Эта функция должна выводить 0, 10, 10, 100, -1, -1, 5, 5, 8, 9, 3, 9, 7, 0
******************************************************************************/
Мой ответ:
/*
My assumptions:
1. There is no guarantee they will be in
sorted order and/or grouped together.
2. You can have at most two instances of the same value,
meaning it's fine if I have one instance.
I feel like the fact that there can be at most two instances
of the same value means that it can be
done in O(N) space and O(1) time... Thinking...
*/
// Naive first solution using more space. O(N) time and O(N) space.
void deduplicatePartial(std::vector<int>& vec) {
vector<int> resVec;
resVec.reserve(vec.size());
unordered_map<int, int> numMap;
for (int i{}; i < vec.size(); ++i) {
auto iter = numMap.find(vec[i]);
if (iter == numMap.end()) { // If I can't find this number in my map,
resVec.push_back(vec[i]); // put it in my result vector.
numMap[vec[i]] = {1}; // Make entry to map.
}
}
vec = std::move(resVec); // Rip its guts out.
//vec = {resVec.begin(), resVec.end()};
}