LeetCode–二维数组中的查找
< 返回列表时间: 2020-07-14来源:OSCHINA
LeetCode–二维数组中的查找
博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!
说明
剑指offer,4题,主站 240题
二维数组中的查找
题目
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 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。
Java
使用线性查找,从右上角开始查找,因为一行的最大值在右上角,如果比当前的值小,那么就向左查询,如果比当前的值大,那么就向右查 class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if(matrix.length == 0 || matrix[0].length == 0){ return false; } int x = 0, y = matrix[0].length - 1; while(x<matrix.length && y>=0){ int num = matrix[x][y]; if(num == target){ return true; }else if(num > target){ y--; }else{ x++; } } return false; } }
Go
使用线性查找,从右上角开始查找,因为一行的最大值在右上角,如果比当前的值小,那么就向左查询,如果比当前的值大,那么就向右查 func findNumberIn2DArray(matrix [][]int, target int) bool { y := len(matrix[0])-1 x := 0 for x<len(matrix) && y>=0{ if matrix[x][y] == target{ return true }else if matrix[x][y] > target{ y-- }else{ x++ } } return false; }
C
使用线性查找,从右上角开始查找,因为一行的最大值在右上角,如果比当前的值小,那么就向左查询,如果比当前的值大,那么就向右查 bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){ int x = 0; int y = matrixSize - 1; while(x<matrixSize && y>=0){ if(matrix[x][y] == target){ return true; }else if(matrix[x][y] > target){ y--; }else{ x++; } } return false; }
PHP
暴力法 class Solution { /** * @param Integer[][] $matrix * @param Integer $target * @return Boolean */ function findNumberIn2DArray($matrix, $target) { if(count($matrix)==0 || count($matrix[0])==0){ return false; } for($i = 0;$i<count($matrix);$i++){ for($j = 0; $j<count($matrix[$i]);$j++){ if($matrix[$i][$j] == $target){ return true; } } } return false; } }
线性查找 class Solution { /** * @param Integer[] $nums * @return Integer */ function findRepeatNumber($nums) { $res = []; for($i=0;$i<count($nums);$i++){ if(isset($res[$nums[$i]])){ return $nums[$i]; } $res[$nums[$i]] = ''; } } }
感谢 leetcode
以及勤劳的自己
热门排行