剑指offer -- 二维数组中的查找

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

暴力查找法:

是一种简单直接的解决方法，可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素，逐个与目标值进行比较。

具体步骤如下：

1. 从数组的第一行第一列开始，逐行逐列地遍历数组的每个元素。
2. 对于当前遍历到的元素，与目标值进行比较：
   • 如果当前元素等于目标值，则找到目标值，返回true。
   • 如果当前元素大于目标值，则可以提前结束查找，因为数组已经按递增顺序排列，后续元素必定更大。
3. 如果遍历完整个数组都没有找到目标值，则说明目标值不存在于数组中，返回false。
4.  时间复杂度为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;  // 目标值不存在于数组中
}

 

题目要求在一个二维数组中查找是否存在某个整数。该二维数组的特点是每一行从左到右递增，每一列从上到下递增。

解决该问题的一个思路是从二维数组的右上角开始比较，根据目标值与当前元素的大小关系，可以逐步缩小查找范围。具体步骤如下：

1. 初始化指针row为0，指向第一行的最后一个元素，指针col为二维数组的列数减1，指向最后一列的第一个元素。
2. 进入循环，比较当前指针指向的元素array[row][col]与目标值target的大小关系：
   • 如果array[row][col]等于target，说明找到了目标值，返回True。
   • 如果array[row][col]大于target，说明目标值可能在当前元素的左侧，将指针col向左移动一列。
   • 如果array[row][col]小于target，说明目标值可能在当前元素的下方，将指针row向下移动一行。
3. 如果指针row或col超出了二维数组的边界，则说明查找范围已经越界，目标值不存在于二维数组中，返回False。
4. 空间复杂度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;  // 输出: truecout << boolalpha << findTarget(array, target2) << endl;  // 输出: falsereturn 0;
}