跳到主要内容

简述Java实现有序矩阵搜索 ?

参考答案:

有序矩阵搜索通常指的是在一个每一行和每一列都已排序的二维矩阵中搜索一个特定的元素。对于这种特定的问题,我们可以使用一种高效的搜索算法,该算法的时间复杂度为O(m+n),其中m和n分别是矩阵的行数和列数。

以下是Java实现有序矩阵搜索的基本步骤:

public class OrderedMatrixSearch {

    public static int searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return -1;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return row;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

        return -1;
    }

    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;
        int result = searchMatrix(matrix, target);
        if (result != -1) {
            System.out.println("Element found at row: " + result);
        } else {
            System.out.println("Element not found in the matrix");
        }
    }
}

这个算法从矩阵的右上角开始搜索。如果当前元素等于目标值,则返回该元素的行索引。如果当前元素大于目标值,则目标值必然在当前元素的左边,因此将列索引减1。如果当前元素小于目标值,则目标值必然在当前元素的下面,因此将行索引加1。重复此过程,直到找到目标值或超出矩阵的范围。如果超出矩阵的范围,则目标值不在矩阵中,返回-1。