【剑指offer】-二维数组的查找-01/67

1. 题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

2. 题目分析

题目中样例大概可为:

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8

2.1. 第一个做法为:

直接暴力遍历,查找有没有该整数的存在,此做法复杂度和时间比较高(不建议)

2.2 第二个做法为:

观察规律,可以得知,在最右上角的数字(5),在整行之中是属于最大的,在整列之中是属于最小的,根据这个规律,可以将整数与右上角数字相比较,若大于则直接换下一行,若小于,则直接换上一列。

3. 代码(java)

3.1 暴力代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public boolean Find(int target, int [][] array)
{
int hang = array.length;
int lie = array[0].length;
for(int i = 0; i < lie; i++)
{
for(int j = 0; j < hang; j++)
{
if(array[i][j] == target)
{
return true;
}
}
}
return false;
}

//运行时间:132ms
//占用内存:17232k

3.2 规律代码:

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
public class Solution {
public boolean Find(int target, int [][] array)
{
int hang = array.length;
int lie = array[0].length;
int j = lie - 1;//代表的是列数
int i = 0;//代表的是行数
while(j >= 0 && i < hang)
{
if(target == array[i][j])
{
return true;
}
else if(target > array[i][j])
{
i++;
}
else if(target < array[i][j])
{
j--;
}
}
return false;
}
}

//运行时间:180ms
//占用内存:17596k

4. 总结

在JAVA中,数组的行数和列数的求算方法为:

1
2
3
4
5
java 是按行存储数组的
假如一个二维数组 array,
它的行数为: array.length
它的列数为: array[0].length
三维数组则分别为: array.length, array[0].length, array[0][0].length
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信