Ctrl K

Сжать таблицу чисел

Сложная
Дана таблица grid размером m × n, все числа в ней положительные и различные. Каждое число нужно заменить положительным целым так, чтобы в любой строке и в любом столбце сохранился порядок: если одно число было больше другого из той же строки или того же столбца, то и после замены оно должно быть больше. Новые значения должны быть как можно меньше: каждая клетка получает 1, если её число наименьшее и в строке, и в столбце, а иначе — на единицу больше наибольшего нового значения среди меньших чисел её строки и её столбца. Такая замена единственная и заодно делает наибольшее число таблицы минимальным. Верните получившуюся таблицу.
Пример 1
grid=[[4, 9], [7, 2]] → [[1, 2], [2, 1]]

2 и 4 — наименьшие в своих строках и столбцах, им достаётся 1. Число 7 больше 2 в своей строке и больше 4 в своём столбце, поэтому получает 2; так же и 9.

Пример 2
grid=[[5, 1, 8]] → [[2, 1, 3]]

В одной строке порядок 1 < 5 < 8 превращается в 1 < 2 < 3.

Пример 3
grid=[[3, 6], [10, 4], [2, 7]] → [[2, 3], [3, 1], [1, 4]]
Ограничения
  • 1 ≤ m, n ≤ 1000, 1 ≤ m · n ≤ 10⁵
  • 1 ≤ grid[i][j] ≤ 10⁹
  • Все числа в grid различны
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиУровни клеток по строкам и столбцам СложнаяСамый длинный подъём по карте СложнаяКаждый цвет — один раз СложнаяПоездки на самокате с лимитом дороги СложнаяМышь, кот и сыр Сложная
загружаем Python…
Вход
grid=[[4, 9], [7, 2]]
Ожидается
[[1, 2], [2, 1]]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 69 тестов на сервере, включая скрытые.