营销型网站建设费用怎么这么大,做网站的,热点新闻事件2023,哪些行业做网站最重要剑指offerWeek1
周三#xff1a;二维数组中的查找
题目链接#xff1a;二维数组中的查找
在一个二维数组中#xff0c;每一行都按照从左到右递增的顺序排序#xff0c;每一列都按照从上到下递增的顺序排序。请完成一个函数#xff0c;输入这样的一个二维数组和一个整数…剑指offerWeek1
周三二维数组中的查找
题目链接二维数组中的查找
在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。数据范围
二维数组中元素个数范围 [0,1000]
样例
输入数组[[1,2,8,9][2,4,9,12][4,7,10,13][6,8,11,15]
]如果输入查找数值为7则返回true如果输入查找数值为5则返回false。AC代码
class Solution {
public:bool searchArray(vectorvectorint array, int target) {if (array.empty() || array[0].empty()) return false;int i 0, j array[0].size() - 1;while (i array.size() j 0){int t array[i][j];if (t target) return true;if (t target) j -- ;else i ;}return false;}
};思路
整体思路
本题可以借鉴游戏俄罗斯方块来理解
在俄罗斯方块中当一行都有方块时则消除该行
抽象一层即满足某个性质消除一行本题中题目直接给出性质每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。
那么可以利用性质给出如下思路
对于目标值x每次都和第一行的最后一个数值进行判断如果目标值x大于第一行的最后一个数值则说明第一行的所有数值都小于目标值x则消除第一行
若目标值x小于第一行的最后一个数值则说明第一列的所有数值都大于目标值x则消除第一列
如此不断往复并且在往复的过程中判断是否是目标值即可代码思路
特判数值是否为空确定行列值while循环循环条件是二维数组中还存在数值 如果目标值x大于第一行的最后一个数值则说明第一行的所有数值都小于目标值x则消除第一行i若目标值x小于第一行的最后一个数值则说明第一列的所有数值都大于目标值x则消除第一列j –如果是目标值则直接返回true 若循环结束都没有找到则返回false
部分模拟
[ [1,2,8,9] [2,4,9,12] [4,7,10,13] [6,8,11,15] ]
如果输入查找数值为7 数组存在 从第一行第四列开始i 0j 3 while循环循环条件是二维数组中还存在数值 第一行第四列数值为9 大于目标值7则第四列的数值都大于目标值7第四列直接舍去j –此时二维数组为 [[1,2,8][2,4,9][4,7,10][6,8,11]
]第一行第三列数值为8 大于目标值7则第三列的数值都大于目标值7第三列直接舍去j –此时二维数组为 [[1,2][2,4][4,7][6,8]
]第一行第二列数值为2 小于目标值7则第一行的数值都小于于目标值7第一行直接舍去i此时二维数组为 [[2,4][4,7][6,8]
]如此往复即可
