提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、搜索二维矩阵 II是什么？
- 二、具体实现
前言
用运scala的语法实现搜索二维矩阵 II
一、搜索二维矩阵 II是什么？
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 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
二、具体实现
代码如下：
def main(args: Array[String]): Unit = {val arr = Array(Array(1, 4, 7, 11, 15),Array(2, 5, 8, 12, 19),Array(3, 6, 9, 16, 22),Array(10, 13, 14, 17, 24),Array(18, 21, 23, 26, 30))println(searchMatrix(Array(Array(1,1)), 2))
}
//本题的思路是从右上角往左下角找。每次比较可以排除一行或者一列，时间复杂度为O(m+n)
def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {if(matrix == null || matrix.length == 0){return false;}val x = matrix.length - 1val y = matrix(0).length - 1var curX = 0var curY = y//定义初始位置为右上角（0，y）当前值如果大于target，向左移一位，//如果当前值小于target，向下移一位while (curX <= x && curY >= 0) {if (matrix(curX)(curY)>target)//当前值如果大于target，向左移一位curY-=1else if(matrix(curX)(curY)<target)//当前值小于target，向下移一位curX+=1else//当前值等于target，返回truereturn true}false
}