数据结构刷题:第十八天(基础)

简介: 由于矩阵matrix 中每一行的元素都是升序排列的,因此我们可以对每一行都使用一次二分查找,判断 target 是否在该行中,从而判断 target 是否出现。

一,搜索二维矩阵


240. 搜索二维矩阵 II - 力扣(LeetCode)

https://leetcode.cn/problems/search-a-2d-matrix-ii/?plan=data-structures&plan_progress=zz5yyb3


231e8cd2ca784511bf697a66d64f6ba6.png


1,二分查找


思路与算法


由于矩阵matrix 中每一行的元素都是升序排列的,因此我们可以对每一行都使用一次二分查找,判断 target 是否在该行中,从而判断 target 是否出现。


class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};


二,无重叠区间


435. 无重叠区间 - 力扣(LeetCode)

https://leetcode.cn/problems/non-overlapping-intervals/?plan=data-structures&plan_progress=zz5yyb3


d6f71efe01924144839060669904b6b7.png


看题解:

目录
相关文章
|
6天前
|
存储 算法 Java
【数据结构与算法】1.数据结构绪论
【数据结构与算法】1.数据结构绪论
|
6天前
|
存储 算法 编译器
【数据结构入门精讲 | 第十一篇】一文讲清树
【数据结构入门精讲 | 第十一篇】一文讲清树
29 0
|
11月前
|
存储 算法 NoSQL
【全面突击数据结构与算法001】绪论篇,数据结构的基本概念
【全面突击数据结构与算法001】绪论篇,数据结构的基本概念
119 0
|
存储 机器学习/深度学习 算法
数据结构刷题:第十五天(基础)
使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数,并更新哈希表,最后遍历哈希表,得到只出现一次的数字。
76 0
数据结构刷题:第十五天(基础)
数据结构刷题:第十七天(基础)
数据结构刷题:第十七天(基础)
49 0
数据结构刷题:第十七天(基础)
|
机器学习/深度学习 存储 C++
数据结构刷题:第十六天(基础)
数据结构刷题:第十六天(基础)
93 0
数据结构刷题:第十六天(基础)
|
机器学习/深度学习 存储 算法
数据结构刷题:第八天
当我们遍历到链表的最后一个节点时,cur.next 为空节点,如果不加以判断,访问 cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点,而不需要遍历完整个链表。
67 0
数据结构刷题:第八天
|
算法
数据结构刷题:第五天
具体地,我们首先遍历该数组一次,如果某个元素为 0,那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组,用标记数组更新原数组即可。
58 0
数据结构刷题:第五天
|
机器学习/深度学习 算法 C++
数据结构刷题:第四天
数据结构刷题:第四天
68 0
数据结构刷题:第四天
|
存储 机器学习/深度学习 算法
数据结构刷题:第十四天
空间复杂度:O(n),其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 n ,递归最深达到 n 层,故最坏情况下空间复杂度为 O(n) 。
58 0
数据结构刷题:第十四天