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

这篇具有很好参考价值的文章主要介绍了剑指offer -- 二维数组中的查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

暴力查找法:

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

具体步骤如下:

  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;  // 目标值不存在于数组中
}

 

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

解决该问题的一个思路是从二维数组的右上角开始比较,根据目标值与当前元素的大小关系,可以逐步缩小查找范围。具体步骤如下:文章来源地址https://www.toymoban.com/news/detail-463816.html

  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. 如果指针rowcol超出了二维数组的边界,则说明查找范围已经越界,目标值不存在于二维数组中,返回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;  // 输出: true
    cout << boolalpha << findTarget(array, target2) << endl;  // 输出: false

    return 0;
}

到了这里,关于剑指offer -- 二维数组中的查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每天一道leetcode:剑指 Offer 53 - I. 在排序数组中查找数字 I(适合初学者&二分查找)

    统计一个数字在排序数组中出现的次数。 0 = nums.length = 10^5 -10^9 = nums[i] = 10^9 nums 是一个非递减数组 -10^9 = target = 10^9 使用两次二分查找找到target在数组中的左右边界,然后长度就是右边界减去左边界再加一,最后返回长度即可。   欢迎大家在评论区讨论,如有不懂的代码部分

    2024年02月14日
    浏览(53)
  • 剑指 Offer 51. 数组中的逆序对

    剑指 Offer 51. 数组中的逆序对   【归并】朴实无华的一个归并排序的应用,对于一个数组,我们通过归并排序来从大到小进行排序,在合并的过程中如果前面区间有比后面区间大的元素,那么后面区间从这个元素开始一直到结束都能和前面区间的那个数组成逆序对。 举个🌰

    2024年02月02日
    浏览(37)
  • (排序) 剑指 Offer 51. 数组中的逆序对 ——【Leetcode每日一题】

    难度:困难 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制 : 0 = 数组长度 = 50000 💡思路:归并排序 预备知识 「 归并排序 」是用 分治 思想,分

    2024年02月11日
    浏览(44)
  • 【题解】二分查找-I、二维数组中的查找

    题目链接:二分查找-I 解题思路:遍历 代码如下: 这种解题思路很明显没有很好的利用题目中强调的数组是升序的,既然是升序,那肯定前半部分偏小,后半部分偏大,如果我们能知道应该去前半部分还是后半部分寻找target,效率相对就提升很多了,于是我们有了下面的分

    2024年02月14日
    浏览(40)
  • 【剑指Offer】--->详解二分查找相关练习

    没有人会为你踏雾而来,喜欢的风景要自己去看。 二分查找相信大家都应该不陌生,本次博主为大家带来的是一些有关二分查找变形的有关题目(来自剑指offer),相信认真读完了后对初学者会有一定的帮助(我也是初学者,各位大佬不要喷我) 目录 ​1 数字在有序数组中出

    2023年04月08日
    浏览(35)
  • 【九章斩题录】C/C++:二维数组中的查找(JZ4)

       精品题解  👉 《九章刷题录》 📜 目录: 「 法一 」暴力美学 「 法二 」十字分割法 「 法三 」逐行二分 📚 题目描述: 在一个二维数组 array 中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一

    2024年02月07日
    浏览(69)
  • 【剑指offer】数据结构——数组

    【剑指offer】03.数组中重复的数字 //03. 数组中重复的数字 // 找出数组中重复的数字。 // 力扣 // 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 // 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每 // 个数字重复了几次。请找出数组中任意一

    2024年02月08日
    浏览(36)
  • 剑指 Offer 66. 构建乘积数组

    给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 。不能使用除法。 示例: 提示: 所有元素乘积之和不会溢出 32 位整数 a.length = 100000 解答

    2024年02月16日
    浏览(49)
  • 《剑指 Offer》专项突破版 - 面试题 13 : 二维子矩阵的数字之和(C++ 实现)- 二维前缀和

    题目链接 :LCR 013. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode) 题目 : 输入一个二维矩阵,如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和?对于同一个二维矩阵,计算子矩阵的数字之和的函数可能由于输入不同的坐标而反复调用多次。 例如,对于下图中的二

    2024年01月18日
    浏览(39)
  • 【剑指 offer】旋转数组的最小数字

    ✨个人主页:bit me👇 ✨当前专栏:算法训练营👇 核心考点:数组理解,二分查找,临界条件 描述: 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这

    2023年04月20日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包