← Назад к вопросам
Поиск в матрице, отсортированной по строкам и столбцам
1.0 Junior🔥 71 комментариев
#Другое#Основы Java
Условие
Дана матрица m x n, в которой каждая строка и каждый столбец отсортированы по возрастанию. Найдите элемент target.
Пример
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
- target = 20 → false
Требования
- Временная сложность O(m + n)
- Начните поиск с правого верхнего или левого нижнего угла
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Поиск в матрице, отсортированной по строкам и столбцам
Анализ задачи
Эта классическая задача собеседования требует глубокого понимания структуры отсортированной матрицы. Ключевое наблюдение: если мы начнём поиск с правого верхнего или левого нижнего угла, можно отбросить целую строку или столбец за один шаг, достигая временной сложности O(m + n).
Интуиция решения
Представим начало с правого верхнего угла матрицы:
[1, 4, 7, 11, 15] ← Начинаем здесь: matrix[0][4] = 15
[2, 5, 8, 12, 19]
[3, 6, 9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]
Логика:
- Если target < текущее число → идём влево (числа здесь меньше)
- Если target > текущее число → идём вниз (числа здесь больше)
- Если target == текущее число → нашли!
Решение 1: Поиск с правого верхнего угла
public class SortedMatrixSearch {
/**
* Поиск элемента в матрице, отсортированной по строкам и столбцам
* Начинаем с правого верхнего угла
*
* Временная сложность: O(m + n)
* Пространственная сложность: O(1)
*
* @param matrix Матрица m x n (отсортирована по строкам и столбцам)
* @param target Искомый элемент
* @return true если элемент найден, false иначе
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int rows = matrix.length; // m
int cols = matrix[0].length; // n
// Начинаем с правого верхнего угла
// matrix[0][cols-1]
int row = 0; // Верхняя строка
int col = cols - 1; // Правый столбец
while (row < rows && col >= 0) {
int current = matrix[row][col];
if (current == target) {
return true; // Элемент найден
} else if (current < target) {
// Текущий элемент меньше target
// Все элементы слева от current тоже меньше
// Нужно идти вниз (в следующую строку)
row++;
} else {
// Текущий элемент больше target
// Все элементы ниже current тоже больше
// Нужно идти влево (в предыдущий столбец)
col--;
}
}
return false; // Элемент не найден
}
}
Решение 2: Поиск с левого нижнего угла
public class SortedMatrixSearchAlt {
/**
* Альтернативное решение: начинаем с левого нижнего угла
* matrix[rows-1][0]
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
// Начинаем с левого нижнего угла
int row = rows - 1; // Нижняя строка
int col = 0; // Левый столбец
while (row >= 0 && col < cols) {
int current = matrix[row][col];
if (current == target) {
return true;
} else if (current < target) {
// Текущий элемент меньше target
// Все элементы выше current тоже меньше
// Нужно идти вправо
col++;
} else {
// Текущий элемент больше target
// Все элементы справа current тоже больше
// Нужно идти вверх
row--;
}
}
return false;
}
}
Визуальная демонстрация алгоритма
public class VisualizationExample {
/**
* Демонстрирует пошаговое выполнение для target = 5
*/
public static void main(String[] args) {
int[][] 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}
};
int target = 5;
System.out.println("Поиск target = " + target);
System.out.println();
int rows = matrix.length;
int cols = matrix[0].length;
int row = 0;
int col = cols - 1;
int step = 0;
System.out.println("Шаги поиска:");
while (row < rows && col >= 0) {
int current = matrix[row][col];
step++;
System.out.printf("Шаг %d: matrix[%d][%d] = %d",
step, row, col, current);
if (current == target) {
System.out.println(" → НАЙДЕНО!");
return;
} else if (current < target) {
System.out.println(" < " + target + " → идём вниз");
row++;
} else {
System.out.println(" > " + target + " → идём влево");
col--;
}
}
System.out.println("\nЭлемент не найден");
}
}
/*
Ожидаемый вывод:
Поиск target = 5
Шаги поиска:
Шаг 1: matrix[0][4] = 15 > 5 → идём влево
Шаг 2: matrix[0][3] = 11 > 5 → идём влево
Шаг 3: matrix[0][2] = 7 > 5 → идём влево
Шаг 4: matrix[0][1] = 4 < 5 → идём вниз
Шаг 5: matrix[1][1] = 5 → НАЙДЕНО!
*/
Тестирование всех случаев
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
public class SortedMatrixSearchTest {
private final SortedMatrixSearch search = new SortedMatrixSearch();
@Test
public void testElementExists() {
int[][] 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}
};
assertTrue(search.searchMatrix(matrix, 5));
assertTrue(search.searchMatrix(matrix, 15));
assertTrue(search.searchMatrix(matrix, 30));
assertTrue(search.searchMatrix(matrix, 1));
assertTrue(search.searchMatrix(matrix, 24));
}
@Test
public void testElementNotExists() {
int[][] 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}
};
assertFalse(search.searchMatrix(matrix, 20));
assertFalse(search.searchMatrix(matrix, 0));
assertFalse(search.searchMatrix(matrix, 31));
assertFalse(search.searchMatrix(matrix, 11.5)); // Не целое число
}
@Test
public void testEdgeCases() {
// Пустая матрица
int[][] emptyMatrix = {};
assertFalse(search.searchMatrix(emptyMatrix, 5));
// Матрица 1x1
int[][] singleElement = {{5}};
assertTrue(search.searchMatrix(singleElement, 5));
assertFalse(search.searchMatrix(singleElement, 3));
// Матрица 1xn
int[][] singleRow = {{1, 2, 3, 4, 5}};
assertTrue(search.searchMatrix(singleRow, 3));
assertFalse(search.searchMatrix(singleRow, 6));
// Матрица mx1
int[][] singleCol = {{1}, {2}, {3}, {4}, {5}};
assertTrue(search.searchMatrix(singleCol, 4));
assertFalse(search.searchMatrix(singleCol, 6));
}
@Test
public void testTimeComplexity() {
// Максимум m + n шагов (в худшем случае пересекаем всю матрицу)
int[][] 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}
};
// Для матрицы 5x5: O(5 + 5) = O(10) операций в худшем случае
assertFalse(search.searchMatrix(matrix, -1)); // Не существует
}
}
Анализ сложности
Временная сложность: O(m + n)
- Начинаем из правого верхнего угла: matrix[0][cols-1]
- На каждом шаге либо row++, либо col--
- Максимум шагов = m (все строки) + n (все столбцы) = m + n
- Каждая операция O(1)
- Итого: O(m + n)
Пространственная сложность: O(1)
- Используем только несколько переменных (row, col, current)
- Не используем дополнительные структуры данных
Почему НЕ может быть O(log m + log n)?
Молодые разработчики часто спрашивают, почему не использовать двоичный поиск.
// ❌ НЕПРАВИЛЬНО - двоичный поиск не работает
public boolean binarySearchWrong(int[][] matrix, int target) {
// Двоичный поиск по всей матрице как на 1D array
// Это может работать, но требует преобразования матрицы
// Временная сложность: O(log(m*n))
// Но это медленнее чем O(m+n) для больших матриц!
return false;
}
Сравнение:
- Поиск с угла: O(m + n)
- Двоичный поиск: O(log(m * n))
Для матрицы 1000x1000:
- O(m + n) = 2000
- O(log(m*n)) = log(1000000) ≈ 20
Пока двоичный поиск выглядит лучше, но на практике:
- Требует линеаризации матрицы
- Сложнее в реализации
- Больше операций на элемент
Поиск с угла — оптимальное решение!
Ключевые выводы
- Начните с угла — правый верхний или левый нижний
- Отбрасывайте строку/столбец на каждом шаге
- O(m + n) — оптимальная временная сложность
- O(1) — минимальная пространственная сложность
- Используйте эту логику в собеседованиях для произведения впечатления