Comments 10
Вместо того что бы выделять новый вектор под ответ, можно отдать уже выделенную память, раз уж нам разрешили менять аргумент.
vector<int> replaceNonCoprimes(vector<int>& nums) {
...
nums.erase(nums.begin() + k, nums.end());
return std::move(nums);
}Memory: Beats 99.62%
Так ведь я об этом написал, и код работает со входным массивом nums :) Поправлю форматирование - вместо маркированного списка поставлю заголовки, чтобы в глаза бросалось.
Способ 1:
NumsVector result;
// копия вектора
Способ 2
Сожмем исходный массив так, что нули окажутся в хвосте, а хвост отстрижем
...
nums[w++] = nums[r];
...
nums.resize(w);
Ваш erase тот же, что мой resize. Я проверил на leetcode: erase работает не выигрывает у resize в памяти. А вот явный вызов std::move(nums) дает Memory 119.64 MB Beats 99.57%. Компилятор часто сам соображает, где оптимизировать возврат с помощью move, но здесь почему-то явный вызов сэкономил память.
Явный std::move еще и ускорил решение - чудеса да и только.
Спасибо за находку :)
Вообще странно модифицировать аргумент функции и при этом возвращать его. А ещё страннее сделать move.
Компилятор не может здесь ничего "оптимизировать" (как минимум без flto), в случае с копированием вектора (без std::move), вы обязаны создать копию, а вектор-аргумент останется не-пустым (и естественно должен указывать на другую память, иначе при вызове деструкторов случился бы "double-free"), в случае с std::move вы перекидываете указатели на уже выделенную память, а вектор аргумент содержит nullptr-ы. Если например тестирующая обертка логгирует size у тестового вектора после вызова нашей функции - то и flto никак не поможет.
Я бы сказал это архетипичный пример мув-семантики, недоступный до её введения в стандарт. До С++11 приходилось делать так:
vector<int> replaceNonCoprimes(vector<int>& nums) {
vector<int> ans;
ans.swap(nums);
...
return ans;
}Работает полностью аналогично, и тут как раз срабатывает корректная оптимизация NRVO (обязательная с C++17), и кстати с таким подходом std::move будет только всё портить.
Строчка с nums.erase только отвлекает, она тут не причём. Главное что мы не просто используем входную память для своих вычислений, а то что мы не выделяем никакую другую.
Ну и если нам разрешают менять аргумент функции, значит и разрешают сделать его пустым, украв его память. И естественно что выкинув из решения аллокацию на полмегабайта оно станет быстрее.
Как же сложно. Вот все решение:
vector<int> replaceNonCoprimes(vector<int>& nums) {
int n = 0;
for (int x : nums) {
nums[n++] = x;
int d;
while (n > 1 && (d = gcd(nums[n-1], nums[n-2])) > 1) {
nums[n-2] = nums[n-2] / d * nums[n-1];
--n;
}
}
nums.resize(n);
return nums;
}Собираем ответ среди первых n ячеек имеющегося массива nums. Поддерживаем инваринт, что там все соседние числа взаимнопросты. Каждое число добавялем туда в конец. Инвариант может быть нарушен только между двумя последними числами. Поэтому проверяем и объединяем 2 последних элемента если надо. Но это надо делать в цикле, потому что новое объединенное число изменилось же, оно опять может нарушить инвариант.
Если a b c идут подряд и a, b взимнопросты, а c и b нет, при замене (c , b) -> на gcd проверять взаимнопростоту с a не надо. gcd точно делит b, значит, тоже не будет иметь общих делителей с a. После этого задача становится однопроходной и тривиальной.
Задачи по алгоритмам: ищем непростые числа