【剑指 offer】二维数组中的查找 --Java实现
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
方法一:暴力查找
- 分析:遍历一遍数组,即可判断目标target是否存在
- 复杂度分析
时间复杂度 O(n^2) 因为在最坏的情况下,数组中的每个元素都需要被遍历一次。
空间复杂度 O(1) - 代码
public class Solution { public boolean Find(int target, int [][] array) { for(int i=0; i<array.length; i++){ for(int j=0; j<array.length; j++){ if(array[i][j] == target) return true; } } return false; } }
方法二:从左下找
- 分析
利用该二维数组的性质:
(1)每一行都是按照从左到右递增的顺序排序
(2)都一列都是按照从上到下递增的顺序排序