1.题目描述
有一个二维数组. 数组的每行从左到右是递增的，每列从上到下是递增的. 在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N);
2.代码展示
#include<iostream>
#include<vector>
using namespace std
;
bool Isin(vector
<vector
<int>> v
,int n
,int m
,int num
)
{
int x
= n
-1, y
= 0;
while (x
>= 0 && x
< n
&&y
>= 0 && y
< m
)
{
int index
= v
[x
][y
];
if (num
>index
)
{
++y
;
}
else if (num
< index
)
{
--x
;
}
else
{
return true;
}
}
return false;
}
int main()
{
int n
= 0, m
= 0;
cin
>> n
>> m
;
vector
<vector
<int>> v(n
);
for (int i
= 0; i
< n
; ++i
)
{
v
[i
].resize(m
);
for (int j
= 0; j
< m
; ++j
)
{
cin
>> v
[i
][j
];
}
}
int num
= 0;
while (cin
>> num
)
{
if (Isin(v
, n
, m
, num
))
{
cout
<< "存在" << endl
;
}
else
{
cout
<< "不存在" << endl
;
}
}
system("pause");
return 0;
}
3.解题思路
由于杨氏矩阵从左向右，从上向下是递增的，所以我们以左下角为初始点，当输入的数据大于这个值时，那么我们可以判断所查找的值一定在当前数据的右边，小于当前值时，一定在当前数据的上方。
Processed:
0.018, SQL:
12
