【手把手带你刷LeetCode】——08.搜索二维矩阵

简介: 搜索二维矩阵

【前言】

今天是力扣打卡第八天!

时间过得好快呀,一转眼又是一年立冬,铁汁们记的保暖哦


原题:搜索二维矩阵

题目描述:

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

【注意】:也就是说,整个二维矩阵都是升序的。


示例1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

 

示例2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false


题解:

【敲黑板】:其实这道题目的重点就在于:一维索引和二维索引间的互换

代码执行:

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    //考虑特殊情况
    if(matrix == NULL || matrixSize == 0){
        return false;
    }
    int row = matrixSize;//行数,这里需要注意一下
    int col = *matrixColSize;//列数
    //将二维索引化解成一维索引
    int left = 0;
    int right = row * col - 1;
    int mid = 0;
    int element = 0;
    while(left <= right){
        mid = left + (right - left) / 2;
        element = matrix[mid / col][mid % col];//将一维索引转化成二维索引,实际上使用的还是二维索引
        if(element > target){
            right = mid - 1;
        }else if(element < target){
            left = mid + 1;
        }else{
            return true;
        }
    }
    return false;
}

复杂度分析 :

时间复杂度:O(logM*N), M和N分别是矩阵的行数和列数

空间复杂度:O(1)

结语:

今天是力扣打卡第8天!

坚持住哦,定个小目标,先不间断打满100天!!

送你一朵小红花啦!!!


相关文章
|
3月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
30天前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
14 2
|
30天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
29天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
30天前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
15 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
3月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2