我的
想法：
- 暴力：按行遍历，比较---O（m*n）
- 折半：行折半查找；有n行，折半n次---- O(nlgn)
问题：
不满足时间复杂度O（m+n）
正确
思路：
- 左下角开始比较
- arr[i][0]>target--往小找，往上走，i--；
- arr[i][0]<target--往大找，往右走，j++；
- arr[i][0]==target，即找到
- 循环截至条件，超出数组边界
适用场景：
迷宫遍历四周：因为行，列有序，会有方向的去遍历
代码
//1暴力方法
//题目：
/*
* 学习到：
* ------写代码
* 1. vector二维数组就像是一个元素为一维数组的数组：arr.size()是二维数组的行数，arr[0].size()是每行的元素个数
* 2. 将普通二维数组给vector容器赋值:matrix.push_back(a[i], a[i]+3);
* 3. vector成员函数push_back的使用，参数可以是值，也可以是迭代器
*/
#include <iostream>
using namespace std;
#include <vector>
//解决方法
class Solution1
{
public:
//方法
//返回目标值的有无，target是否在二维数组中
bool find(vector<vector<int>> array, int target) {
for (int i = 0; i < array.size(); i++) {
if (array[i][0] > target) {
break;
}
for (int j = 0; j < array[0].size(); j++) {
if (array[i][j] == target) {
return true;
}
else if (array[i][j] > target) {
break;
}
}
}
return false;
}
};
//没有返回值--打印二维数组
void printMatrix(const vector<vector<int>> matrix) {
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
//主函数
int main1()
{
int a[][4] = { {1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15} };
int target = 0;
vector<vector<int>> nums;
for (int i = 0; i < 4; i++) {
nums.push_back(vector<int>(a[i], a[i] + 4));
}
//printMatrix(nums);
Solution1 solution;
cout << solution.find(nums, 14) << endl;
return 0;
}
//分割线----------
//2折半法
//题目：
#include <iostream>
using namespace std;
#include <vector>
//解决方法
class Solution3
{
public:
//方法
bool find(int target, vector<vector<int>> nums) {
for (int i = 0; i < nums.size(); i++) {
int low = 0;
int high = nums.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[i][mid] == target) {
return true;
}
if (nums[i][mid] > target) {
high = mid - 1;
continue;
}
if (nums[i][mid] < target) {
low = mid + 1;
continue;
}
}
}
return false;
}
};
//主函数
int main3()
{
//测试
int a[][4] = { {1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15} }; //4*4
int target = 7; //目标值
//创建vector二维数组容器
vector<vector<int>> nums;
//使用迭代器循环赋值
for (int i = 0; i < 4; i++) {
nums.push_back(vector<int>(a[i], a[i] + 4));
}
Solution3 solution; //对象实例化
cout << solution.find(target, nums) << endl; //输出结果
return 0;
}
//----分割线
//3. 数组O（m+n）遍历法
//题目：
/*
* 学习到：
* 代码------
* 1. 行，列数：rowCount, colCount
* 2. Solution类在全局区，多个文件相同类或函数会冲突
* 3. 代码调试，一定是自己错了，不要怀疑其他的。函数没执行，需要跳出本类的函数思维限制，去找其他的可能出现错误的地方
* 思路------
* 1. 先缕清执行一次的流程
* 2. 再思考循环，循环条件，变量维护
* 3. 再思考特殊情况
* 4. 再思考通用代码编写
*/
#include <iostream>
using namespace std;
#include <vector>
//解决方法
class Solution2
{
public:
//方法
//返回0or1，代表target是否在该数组中
bool find(int target, vector<vector<int>> nums) {
//行，列数
int rowCount = nums.size();
int colCount = nums[0].size();
//cout << 2 << endl;
//最初比较的元素下标值
int i = rowCount - 1;
int j = 0;
//循环：元素与目标值大小
while (i >= 0 && j < colCount) {
if (nums[i][j] > target) {
i--;
}
else if (nums[i][j] < target){
j++;
}
else {
return true;
}
}
return false;
}
};
//主函数
int main()
{
//测试
int a[][4] = { {1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15} }; //4*4
int target = 7; //目标值
//创建vector二维数组容器
vector<vector<int>> nums;
//使用迭代器循环赋值
for (int i = 0; i < 4; i++) {
nums.push_back(vector<int>(a[i], a[i] + 4));
}
Solution2 solution; //对象实例化
cout << solution.find(target, nums) << endl; //输出结果
return 0;
}
学习到
------写代码过程
- vector二维数组就像是一个元素为一维数组的数组：arr.size()是二维数组的行数，arr[0].size()是每行的元素个数
- 将普通二维数组给vector容器赋值:matrix.push_back(a[i], a[i]+3);
- vector成员函数push_back的使用，参数可以是值，也可以是迭代器
- 行，列数：rowCount, colCount
------调试过程
- 多文件编写时，全局区创建的几个类名，以及成员方法名相同，会造成主函数调用方法不确定是哪一个的问题----类名or成员方法名需要有区别
Solution类在全局区，多个文件相同类或函数会冲突 - 调试需要静下心来去思考，然后再行动；需要精准察觉问题所在
-----——代码经验
- 思路------
-
- 先缕清执行一次的流程
-
- 再思考循环，循环条件，变量维护
-
- 再思考特殊情况
-
- 再思考通用代码编写