ДЕЛО 012: Сглаживание матрицы
На этой неделе мы вернемся к матрицам, потому что они такие забавные. Просто так весело.
Данная проблема не так сложна, как проблемы, которые мы решали раньше, например Rotate Image Matrix или Minimum Time Visiting All Points, но все же дает хорошее упражнение по различным способам работы с данными в 2D-матрице.
Итак, приступим к решению.
ЭТА ПРОБЛЕМА
Вот ссылка на проблему на LeetCode
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in grid.
ОГРАНИЧЕНИЯ
Ограничения, которые мы получаем, являются вашим стандартным набором ограничений для задач, связанных с двумерными матрицами. На данный момент это то, чего мы и ожидали. Но, как всегда, рекомендуется пройти через каждое ограничение, чтобы убедиться, что мы знаем, с чем имеем дело:
m == grid.length
Поскольку нам дана m * n матрица grid, количество строк и столбцов в данной матрице линейно независимы. У нас могло быть больше строк, чем столбцов, и у нас могло быть больше столбцов, чем строк. m представляет количество строк, которое мы должны ожидать для любой данной матрицы.
n == grid[i].length
n представляет ожидаемое количество столбцов. Здесь тоже ничего необычного.
1 <= m, n <= 100
Здесь мы получаем верхний и нижний пределы того, сколько строк или столбцов мы должны ожидать. Имея нижний предел 1 <=, мы можем полагаться на тот факт, что нам не придется беспокоиться об обработке пустых строк или столбцов. Верхний предел не так важен, но если мы захотим придумать несколько пользовательских тестовых случаев, верхний предел <= 100 даст нам достаточно информации для этого.
-100 <= grid[i][j] <= 100
grid[i][j] представляет каждый элемент в матрице, и это ограничение дает нам верхний и нижний предел для каждого элемента. Поскольку это проблема, связанная со значениями каждого элемента и тем, является ли элемент отрицательным числом, нижний предел -100 <= имеет полный смысл, как и верхний предел <= 100. Приятно осознавать, что нам не придется обрабатывать действительно большие числа.
ИСПЫТАНИЯ
ПРОРЫВ
Объяснение и масштаб проблемы довольно просты, хотя может оказаться, что в рукаве есть несколько хитростей. Итак, как обычно, давайте разберем каждую строку объяснения проблемы, поищем любые подсказки, которые могут привести нас к решению, и убедимся, что мы понимаем, что нам нужно решить:
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.
Прямо и по делу. Просто так, как мне нравится. Давайте разберем эту первую часть еще дальше, поскольку нам было дано много информации в одном предложении:
Given a m * n matrix grid
Given a m * n matrix grid просто означает, что количество строк и столбцов в данной матрице не зависит друг от друга. Это по секрету говорит мне, что, хотя некоторые из наших тестовых примеров могут иметь равное количество строк и столбцов, другие могут не иметь, и мы не можем выполнять итерацию по строкам и столбцам одновременно. Если мы захотим это сделать, нам придется найти другое решение.
sorted in non-increasing order
sorted in non-increasing order - это еще один способ сказать sorted in a decreasing order, который является еще одним способом сказать «Числа становятся все меньше». Это очень помогает и говорит мне, что у нас нет беспокоиться о том, чтобы придумать способ сортировки элементов в grid или grid[i]. Работа за нас уже сделана.
both row-wise and column-wise
Это даже более полезно, чем расположение элементов в невозрастающем порядке. Сортируется не только каждая строка, но и каждый столбец. Это означает, что первый элемент в матрице всегда будет наибольшим числом во всей матрице, а последнее число в матрице всегда будет наименьшим (или наиболее отрицательным) числом во всей матрице.
Если мы посмотрим на тестовый пример №1, мы увидим это сами:
[ 4, 3, 2, -1] [ 3, 2, 1, -1] [ 1, 1,-1, -2] [-1,-1,-2,-3]
~
Return the number of negative numbers in grid.
Вот вкратце наша задача. Нам нужно найти эффективный способ итерации по заданной матрице и определить, является ли элемент отрицательным или положительным.
ПОДОЗРЕВАЕМЫЕ
Я придумал два разных, но похожих решения: одно с вложенным циклом, а другое со сплющенной матрицей. И то, и другое будет проходить через grid уникальным образом, но по-прежнему будет давать результаты, которых мы ищем.
Поскольку нам нужно определить, является ли число отрицательным, мы можем использовать Math.sign(). Math.sign() будет return 1, если число положительное, 0, если число равно нулю, и -1, если число отрицательное.
Нам также нужно return количество отрицательных чисел в матрице, и мы можем отслеживать это с помощью переменной-счетчика.
Но все, что нас волнует, - это отрицательное число. 0 и положительные числа значения не имеют. Итак, если Math.sign(<a number>) === -1, мы увеличиваем счетчик.
На этом сходство наших двух решений заканчивается. Поскольку наша задача довольно проста, мы можем обратить наше внимание на поиск эффективного способа итерации по заданной матрице.
Мы можем использовать два подхода:
Решение №1: обратная вложенная итерация
Если мы не хотим изменять grid, мы можем использовать порядок данной матрицы в наших интересах. Поскольку grid сортируется в невозрастающем порядке как по строкам, так и по столбцам, мы можем перебирать каждый подмассив grid, начиная с последнего элемента в grid. Здесь мы, скорее всего, найдем подмассив с отрицательными числами. Мы также можем начать с последнего элемента в каждом подмассиве grid[i][j], поскольку именно там мы, скорее всего, также найдем отрицательное число.
Начиная с конца grid и в конце grid[i], мы можем пройти через grid[i] и проверить, Math.sign(grid[i][j]) === -1, и, если да, увеличить наш счетчик.
Если Math.sign(grid[i][j]) !== -1, то grid[i][j] должно быть положительным числом (или 0), и поскольку grid[i] отсортирован в невозрастающем порядке, мы больше не найдем отрицательных чисел в grid[i], а остальная часть подмассива должна быть заполнена положительными числами.
Как только Math.sign(grid[i][j]) !== -1, мы можем выйти из итерации.
Единственная проблема с этим решением заключается в том, что нам нужно будет вложить итерацию для доступа к grid[i][j], а в худшем случае она будет выполняться за O(n²) время.
Я думаю, мы можем добиться большего.
Решение №2: сглаженная одиночная итерация
Таким образом, невозрастающий порядок grid имеет значение только в контексте строк и столбцов. Что ж, поскольку все, что нам нужно сделать, это определить, отрицательно ли число, порядок значения не имеет. Что, если мы выбросим все строки и столбцы и просто сгладим матрицу?
Если мы сгладим grid и установим сглаженную матрицу на переменную, называемую чем-то вроде flatGrid, мы можем использовать одну итерацию, чтобы пройти через flatGrid и запустить тот же оператор if, что и в первом решении. Это означает, что нам нужно будет проверить каждый элемент, чтобы не прервать итерацию.
Мы могли бы сортировать flatGrid, но если мы вызовем .sort() для flatGrid, мы фактически увеличим нашу временную сложность, поскольку .sort() обычно использует методы слияния и быстрой сортировки в зависимости от среды выполнения. Оба метода обычно выполняются за O(n log n) время, хотя сортировка слиянием завершится через O(n²) время, если flatGrid начнет увеличиваться.
Так что на самом деле было бы быстрее перебирать несортированный плоский массив, учитывая наше ограничение 1 <= m, n <= 100.
Мы также можем использовать [].concat.apply([], grid) вместо grid.flat(), поскольку это более эффективный способ сглаживания массива, когда мы заранее не знаем его длину.
КОД ПСЕВДО
Теперь, когда мы проработали пару решений, давайте попробуем написать псевдокод, прежде чем вставлять что-либо в код:
Решение №1: обратная вложенная итерация
Решение №2. Сглаженная одиночная итерация
Отлично.
КОД
Теперь, когда мы выяснили, как должны работать оба наших решения, давайте посмотрим, работают ли они:
Решение №1: обратная вложенная итерация
Во-первых, давайте определим нашу переменную счетчика count:
Теперь давайте настроим две наши for петли. Оба они начинаются с конца grid и grid[i] соответственно:
Затем все, что нам нужно сделать, это добавить логику, которая проверяет, является ли число отрицательным, увеличивает count, если это так, и прерывает итерацию, если это не так:
Наконец, давайте добавим наше значение return:
Посмотрим, работает ли это:
Отлично.
Решение №2. Сглаженная одиночная итерация
Еще раз, давайте определим count переменную, а также нашу плоскую grid переменную flatGrid:
Затем давайте настроим наш for in цикл на итерацию flatGrid:
Затем мы можем добавить ту же логику, которая проверяет, является ли число отрицательным, и увеличивает на count от первого решения:
Наконец, мы можем добавить наше значение return:
Посмотрим, работает ли это тоже:
Отлично.
ЗАКЛЮЧИТЕЛЬНЫЕ РЕШЕНИЯ
Давайте в последний раз взглянем на наши решения без комментариев и очистим наш синтаксис:
Решение №1: обратная вложенная итерация
Решение №2. Сглаженная одиночная итерация
Отлично.
ЗАДАНИЕ ВЫПОЛНЕНО
Хотя countNegatives не самая сложная или сложная проблема, я подумал, что оба решения, которые мы придумали, были разными и достаточно интересными, чтобы заслужить блог о решении проблемы countNegatives.
Я определенно понимаю, что мои решения не будут лучшими или наиболее эффективными, но я надеюсь, что они помогут вам или кому-то еще найти способ решить проблему, с которой вы столкнетесь на этом пути, который мы называем JavaScript.
В любом случае, я надеюсь, что вы получили некоторую полезную информацию, пусть все ваши функции вернут истину, а все ваши запросы будут отвечать 200.
Оставайся в безопасности ... оставайся здоровым ... и продолжай вести добрый бой.
Уровень кодирования
Спасибо, что стали частью нашего сообщества! Подпишитесь на наш канал YouTube или присоединитесь к Интервью по программированию Skilled.dev.
