← К задачам Матрица: 0/18 решено

5252. Поиск в упорядоченной матрице II

Medium 1 решил

Дана таблица matrix из целых чисел и число target. В каждой строке числа растут слева направо. В каждом столбце — сверху вниз.

1  4  7
2  5  8
3  6  9

вправо числа растут:  1 → 4 → 7,   2 → 5 → 8,   3 → 6 → 9
вниз   числа растут:  1 → 2 → 3,   4 → 5 → 6,   7 → 8 → 9

а если читать как книгу, строка за строкой:
1, 4, 7, 2, 5, 8, 3, 6, 9
         ↑
         после 7 сразу 2 — меньше, чем 7.
получился не отсортированный список.

Поэтому таблицу нельзя склеить в один массив и искать там бинарным поиском (так можно в задаче «Поиск в отсортированной матрице», здесь — нет).

Верните true, если target есть хотя бы в одной клетке, иначе false.

Посмотреть каждую клетку — правильный ответ, и при размере до 300×300 такой перебор даже успеет по времени. Смысл задачи — найти эффективную стратегию: пользоваться сразу двумя порядками (и по строке, и по столбцу), чтобы за шаг отбрасывать целую строку или целый столбец, а не перебирать все m·n клеток.

Примеры:

Вход:

{"matrix": [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], "target": 5}

Выход: true

Объяснение: Во второй строке стоит 5. Есть в таблице → true. Полный перебор тоже нашёл бы эту клетку.

Вход:

{"matrix": [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], "target": 20}

Выход: false

Объяснение: Числа 20 нет: рядом 19 и 21, но в разных местах, и 20 между ними не стоит. Ответ false.

Вход: {"matrix": [[1]], "target": 1}

Выход: true

Объяснение: Одна клетка, она равна target → true.

Ограничения:

1 <= m, n <= 300 -10^9 <= matrix[i][j], target <= 10^9

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!

Решите эту задачу в браузере

Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.