不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

剑指 Offer 04.二维数组中的查找

题目

力扣-剑指 Offer 04. 二维数组中的查找

我的复述:
有一个二维数组

它满足从左往右,从上到下递增的规律,也就是说越接近左上角的数字越小,越接近右下角的数字就越大,现在我们要实现一个高效的算法(函数),查找这个二维数组中是否存在某个值,存在就返回true,不存在返回false

题解

暴力法

先用一个循环,每次遍历出一个数组nums,然后用sort.SearchInts查出nums数组中target的下标,接着做下判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
//Go实现
func findNumberIn2DArray(matrix [][]int, target int) bool {
for _, nums := range matrix {
//遍历数组切片,查找数组中是否含有target值,如果查找不到,返回值是target应该插入数组的位置(会保持数组的递增顺序)
i := sort.SearchInts(nums, target) //查找nums数组中target的下标
//插入的位置小于数组长度 且 插入数组的位置上的值和目标值相等
if i < len(nums) && target == nums[i] {
return true
}
}
return false
}

leetcode-cn执行:

1
2
3
执行用时:
28 ms, 在所有 Go 提交中击败了80.58%的用户
内存消耗:6.6 MB, 在所有 Go 提交中击败了70.78%的用户

牛客网运行:

1
2
3
4
运行时间:7ms
超过8.42%用Go提交的代码
占用内存:3204KB
超过44.21%用Go提交的代码

双指针

举例,查找数字8:

先让指针ij都集中在左下角18的位置上,当发现18>8,那就说明18这一整行都大于8,因此将指针i向上移动一个位置;
当发现10>8,那就说明10这一整行都大于8,因此将指针i向上移动一个位置;
当发现3<8,那就说明从数字3往上这一列,都比目标值8要小,因此将指针j向右移动一个位置;
当发现6<8,说明从数字6往上这一列,都比目标值8要小,因此将指针j向右移动一个位置;
当发现9>8,说明数字9向右边一整行的数字都大于8,因此将指针i向上移动一个位置;
当发现8=8,说明目标值8是存在的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//java实现
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//从数组的左下角位置开始去搜索整个二维数组
//1,当发现当前遍历的元素大于target时,意味着这个元素后面的所有元素也都大于target,那么就不用去搜索这一行了
//2,当发现当前遍历的元素小于target时,意味着这个元素上面的所有元素也都小于target,那么就不用去搜索这一列了

//初始化i和j为数组左下角元素
//最后一行
int i = matrix.length - 1;

//第0列
int j = 0;

//从数组的左下角开始出发,只要 i 和 j 没有越界继续判断
while(i >= 0 && j < matrix[0].length) {
//当发现当前遍历的元素大于target时,意味着这个元素后面的所有元素也都大于target
if (matrix[i][j] > target) {
//行索引向上移动,即i--,即消去矩阵第i行元素
i--;
//当发现当前遍历的元素小于target时,意味着这个元素的所有元素也都小于target
} else if (matrix[i][j] < target) {
//列索引向右移动一格,即j++,即消去矩阵第j列元素
j++;
//否则,说明找到目标值
} else {
return true;
}
}

return false;
}
}

leetcode-cn执行用时

1
2
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:47.3 MB, 在所有 Java 提交中击败了31.35%的用户
------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!