Интересная штука попалась:
https://leetcode.com/problems/set-matrix-zeroes/
Задача - обнулить те строки и столбцы матрицы N x M, в которых встречается хотя бы один ноль.
Естественно, проблема мгновенно решается с временным буфером размером O(N x M), после 5 секунд раздумий уже хватает памяти O(N + M) - учёт обнуляемых строк и столбцов в отдельных одномерных массивах длины M и N, соответственно, - но это неспортивно. А вот чтобы сделать O(1), я думал больше суток. Не всё время, конечно, ещё надо когда-то работать и спать... Искал идеи на stackoverflow - без толку, там другие задачи (например, матрица из единиц и нулей, и решение не подходит).
Интересно, здесь кто-то сможет решить с памятью O(1)? Для разнообразия от игровых движков и поиска подстрок в строке...
Есть способ, который правда займет побольше времени. Учитывая что максимальный размер 200*200 - вполне за разумное время можно найти любое число, которое не встречается в текущей матрице и принять его за мнимый ноль. Дальше все просто - от каждого нуля помечать во все стороны числа, отличные от нуля - мнимым нулем. А в конце - заменить все мнимые нули - настоящими нулями.
PS: а какое решение предложено для булевой матрицы на стакфлоу? По моему оно сложнее моего, ибо там мнимого нуля не найти)
Решение на O(2)
На первом проходе находим и запоминаем с помощью ассистента индексы нулевых элементов.
На втором проходе обнуляемся.
Ассистент хранит индексы в хеш-таблице, в которой время поиска заданного индекса константное и составляет O(1).
#include
#include
#include
using namespace std;
class Solution {
public:
void setZeroes(vector& matrix) {
const auto rows = matrix.size();
const auto columns = matrix[0].size();
Assistant assistant;
for (size_t i = 0; i < rows; ++i) {
for (size_t j = 0; j < columns; ++j) {
if (matrix[i][j] == 0) {
if (!assistant.rows.contains(i)) {
assistant.rows.insert(i);
}
if (!assistant.columns.contains(j)) {
assistant.columns.insert(j);
}
}
}
}
for (size_t i = 0; i < rows; ++i) {
for (size_t j = 0; j < columns; ++j) {
if (assistant.rows.contains(i) || assistant.columns.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
private:
struct Assistant {
unordered_set rows;
unordered_set columns;
};
};
void showMatrix(const vector& matrix) {
for (const auto& row : matrix) {
for (const auto value : row) {
cout
Сам спросил сам и ответил
так что поиск стандартной функцией STL и потом присвоение вектору в матрице вектора с заранее нулевыми значениями. Иначе используем динамику с итерацией указателей для улучшения алгоритма поиска и замены )))
void setZeroes(vector<vector<int>>& matrix) { }