当前位置：首页 > news >正文

左神算法之有序二维矩阵中的目标值查找

news 2025/6/26 9:56:18

有序二维矩阵中的目标值查找

1. 题目描述

给定一个元素为非负整数的二维数组matrix，其中：

每一行按照从左到右递增的顺序排列
每一列按照从上到下递增的顺序排列

再给定一个非负整数aim，请判断aim是否存在于matrix中。

示例：

int[][] matrix = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}
};
int aim = 5; // 返回true
int aim = 15; // 返回false

2. 问题解释

矩阵行列均有序，但不像完全排序的一维数组那样可以直接二分
需要利用行列有序的特性设计高效查找算法
暴力搜索时间复杂度为O(m*n)，不够高效
目标是设计优于O(m*n)的算法

3. 解决思路

方法一：逐行二分查找（适合行数较少的情况）

对每一行进行二分查找
时间复杂度：O(m log n)，m为行数，n为列数

方法二：利用行列有序特性（最优解）

从矩阵的右上角开始查找（或左下角）
比较当前元素与目标值：
- 如果等于目标值，返回true
- 如果大于目标值，排除当前列（向左移动）
- 如果小于目标值，排除当前行（向下移动）
时间复杂度：O(m + n)

4. 代码实现

public class SearchInSortedMatrix {// 方法一：逐行二分查找public boolean searchMatrixByRowBinarySearch(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}for (int[] row : matrix) {if (binarySearch(row, target)) {return true;}}return false;}private boolean binarySearch(int[] row, int target) {int left = 0, right = row.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (row[mid] == target) {return true;} else if (row[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}// 方法二：利用行列有序特性（最优解）public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int row = 0;int col = matrix[0].length - 1; // 从右上角开始while (row < matrix.length && col >= 0) {if (matrix[row][col] == target) {return true;} else if (matrix[row][col] > target) {col--; // 排除当前列} else {row++; // 排除当前行}}return false;}public static void main(String[] args) {SearchInSortedMatrix solution = new SearchInSortedMatrix();int[][] matrix = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};System.out.println(solution.searchMatrix(matrix, 5)); // trueSystem.out.println(solution.searchMatrix(matrix, 15)); // falseSystem.out.println(solution.searchMatrixByRowBinarySearch(matrix, 9)); // trueSystem.out.println(solution.searchMatrixByRowBinarySearch(matrix, 20)); // false}
}