网站建设类型有哪些方面,中铁建设集团门户网登录不上去,马鞍山网站建设价格,互联网公司营业执照经营范围二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 暴力查找法: 是一种简单直接的解决方法#xff0c;可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素#xff0c;逐个与目标值进行比较。 具体步骤如下#xff1a; 从数组的第一行第一列开始#xff0c;…二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 暴力查找法: 是一种简单直接的解决方法可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素逐个与目标值进行比较。 具体步骤如下 从数组的第一行第一列开始逐行逐列地遍历数组的每个元素。对于当前遍历到的元素与目标值进行比较 如果当前元素等于目标值则找到目标值返回true。如果当前元素大于目标值则可以提前结束查找因为数组已经按递增顺序排列后续元素必定更大。如果遍历完整个数组都没有找到目标值则说明目标值不存在于数组中返回false。 时间复杂度为O(m * n) bool searchMatrix(vectorvectorint matrix, int target) {for (int i 0; i matrix.size(); i) {for (int j 0; j matrix[i].size(); j) {if (matrix[i][j] target) {return true; // 找到目标值} else if (matrix[i][j] target) {return false; // 提前结束查找}}}return false; // 目标值不存在于数组中
}对于有序的二维数组我们可以利用二分查找法进行查找目标值。 算法步骤 1. 初始化指针将左上角的元素作为起始点将右下角的元素作为终止点。初始时起始点为数组的左上角元素终止点为数组的右下角元素。 2. 在每一次迭代中将搜索区域一分为二找到中间元素可以选择行中间或列中间的元素。 3. 将目标值与中间元素进行比较 - 如果中间元素等于目标值则找到目标值返回true。 - 如果中间元素大于目标值则目标值可能在中间元素的左侧或上方将搜索区域缩小为左上方的子区域即终止点变为中间元素的左上方元素。 - 如果中间元素小于目标值则目标值可能在中间元素的右侧或下方将搜索区域缩小为右下方的子区域即起始点变为中间元素的右下方元素。 4. 重复执行步骤2和步骤3直到找到目标值或搜索区域为空起始点超过终止点为止。 5. 如果最终搜索区域为空说明目标值不存在于数组中返回false。 6.时间复杂度cols*log(rows) bool searchMatrix(vectorvectorint matrix, int target) {if (matrix.empty() || matrix[0].empty()) {return false; // 处理空数组的情况}int rows matrix.size();int cols matrix[0].size();int left 0;int right rows * cols - 1;while (left right) {int mid left (right - left) / 2;int midValue matrix[mid / cols][mid % cols];if (midValue target) {return true; // 找到目标值} else if (midValue target) {left mid 1; // 目标值可能在中间元素的右侧或下方} else {right mid - 1; // 目标值可能在中间元素的左侧或上方}}return false; // 目标值不存在于数组中
} 题目要求在一个二维数组中查找是否存在某个整数。该二维数组的特点是每一行从左到右递增每一列从上到下递增。 解决该问题的一个思路是从二维数组的右上角开始比较根据目标值与当前元素的大小关系可以逐步缩小查找范围。具体步骤如下 初始化指针row为0指向第一行的最后一个元素指针col为二维数组的列数减1指向最后一列的第一个元素。进入循环比较当前指针指向的元素array[row][col]与目标值target的大小关系 如果array[row][col]等于target说明找到了目标值返回True。如果array[row][col]大于target说明目标值可能在当前元素的左侧将指针col向左移动一列。如果array[row][col]小于target说明目标值可能在当前元素的下方将指针row向下移动一行。如果指针row或col超出了二维数组的边界则说明查找范围已经越界目标值不存在于二维数组中返回False。空间复杂度O(mn) #include iostream
#include vectorusing namespace std;bool findTarget(vectorvectorint array, int target) {if (array.empty() || array[0].empty()) {return false;}int rows array.size();int cols array[0].size();int row 0;int col cols - 1;while (row rows col 0) {if (array[row][col] target) {return true;} else if (array[row][col] target) {col--;} else {row;}}return false;
}int main() {vectorvectorint array {{1, 2, 8, 9},{2, 4, 9, 12},{4, 7, 10, 13},{6, 8, 11, 15}};int target1 7;int target2 3;cout boolalpha findTarget(array, target1) endl; // 输出: truecout boolalpha findTarget(array, target2) endl; // 输出: falsereturn 0;
}
