Уровень: easy
Не так часто сталкиваюсь с матрицами, поэтому захотела записать для себя задачку. Решение у нее элементарное - любимый бинарный поиск👉
Но сначала условие:
Дана матрица чисел размер m x n, отсортированная по убыванию в обоих разрезах: и по столбцам, и по строкам. Нужно подсчитать количество отрицательных чисел в матрице.
Пример матрицы:
5 4 2 1
3 2 1 -1
2 -1 -2 -3
1 -2 -3 -5
Ответ: 7 (количество отрицательных чисел)
Ограничения:
1.m - кол-во строк, n - кол-во столбцов (в коде я назову их rows, cols - так понятнее, на мой взгляд)
2. 1 <= n, m <= 100
3. -100 <= grid[i][j] <= 100
Ссылочка на задачу, как всегда
Итак, погнали алгоритм:
1. Для каждой строки применяем бинарный поиск, чтобы найти индекс первого отрицательного числа (кстати, про бинарный поиск писала статейку на хабре)
UPD:
- если первый элемент строки отрицательный, то все числа на этой строке и на следующих будут отрицательными, поэтому высчитываем кол-во отрицательных здесь и завершаем цикл.
- если последний элемент строки положительный, то можно пропустить всю строку, т.к. элементы слева будут тоже положительными
2. Все числа справа от найденного индекса также будут отрицательными, поэтому сразу добавляем их количество к общему счётчику.
Код:
public int countNegatives(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int negatives = 0;
for (int i = 0; i < rows; i++) {
if (grid[i][0] < 0) {
negatives += (rows - i) * cols;
break;
}
if (grid[i][cols - 1] > 0) {
continue;
}
int left = 0;
int right = cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (grid[i][mid] < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
negatives += cols - left;
}
return negatives;
}Временная сложность: O(m x log n) - т.к. мы будем совершать двоичный поиск в каждой строке (их m штук), и скорость поиска в каждой строке будет O(log n)
Пространственная сложность: O(1) - т.к. выделяется константное кол-во памяти под переменные negatives, left, right, mid, cols, rows