LeetCode 74 Search a 2D Matrix(搜索2D矩阵)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50776497 翻译写一个高效算法用于在一个m x n的矩阵中查找一个值。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50776497

翻译

写一个高效算法用于在一个m x n的矩阵中查找一个值。
这个矩阵有如下属性:

每行的整型数都是从左到右排序的。
每行的第一个元素都比上一行的最后一列大。

例如,
考虑如下矩阵:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
给定target = 3,返回true

原文

Write an efficient algorithm that searches for a value in an m x n matrix. 
This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

分析

可能因为我好困了,所以不论是算法还是我自己,都效率很低……

下面这个代码也是一改再改……

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix[0][0] > target) return false;
    for (int i = 0; i < matrix.size(); ) {
        for (int j = 0; j < matrix[i].size(); ) {
            if (i == matrix.size() - 1 && matrix[i][j] < target) {
                if (j >= matrix[i].size()) return false;
                j += 1;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i+1][j] > target) {
                j += 1;
                if (j >= matrix[i].size()) return false;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i + 1][j] <= target) {
                i += 1;
            }
            else if (matrix[i][j] == target) {
                return true;
            }     
            if (i == matrix.size() - 1 && j == matrix[i].size() ) {
                return false;
            }
        }
    }
    return false;
}

明天再整理整理思路重新做一遍吧……

目录
相关文章
|
3月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
27天前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
14 2
|
27天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
16 0
Leetcode第三十三题(搜索旋转排序数组)
|
26天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
27天前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
14 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实现代码。
106 2