二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)
暴力查找法:
是一种简单直接的解决方法,可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素,逐个与目标值进行比较。
具体步骤如下:
- 从数组的第一行第一列开始,逐行逐列地遍历数组的每个元素。
- 对于当前遍历到的元素,与目标值进行比较:
- 如果当前元素等于目标值,则找到目标值,返回true。
- 如果当前元素大于目标值,则可以提前结束查找,因为数组已经按递增顺序排列,后续元素必定更大。
- 如果遍历完整个数组都没有找到目标值,则说明目标值不存在于数组中,返回false。
- 时间复杂度为O(m * n)
bool searchMatrix(vector<vector<int>>& 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(vector<vector<int>>& 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; // 目标值不存在于数组中 }
题目要求在一个二维数组中查找是否存在某个整数。该二维数组的特点是每一行从左到右递增,每一列从上到下递增。文章来源:https://www.toymoban.com/news/detail-463816.html
解决该问题的一个思路是从二维数组的右上角开始比较,根据目标值与当前元素的大小关系,可以逐步缩小查找范围。具体步骤如下:文章来源地址https://www.toymoban.com/news/detail-463816.html
- 初始化指针
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(m+n)
#include <iostream> #include <vector> using namespace std; bool findTarget(vector<vector<int>>& 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() { vector<vector<int>> 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; // 输出: true cout << boolalpha << findTarget(array, target2) << endl; // 输出: false return 0; }
到了这里,关于剑指offer -- 二维数组中的查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!