LeetCode C++ 剑指 Offer 53 - I. 在排序数组中查找数字 I【二分】简单
发布日期:2021-07-01 02:50:57
浏览次数:2
分类:技术文章
本文共 1969 字,大约阅读时间需要 6 分钟。
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6输出: 0
限制: 0 <= 数组长度 <= 50000
思路1:使用哈希表计数,完全没有利用到题目的条件。代码如下:
class Solution { public: int search(vector & nums, int target) { unordered_mapmp; for (const auto i : nums) ++mp[i]; return mp[target]; }};
效率:
执行用时:16 ms, 在所有 C++ 提交中击败了89.16% 的用户内存消耗:13.4 MB, 在所有 C++ 提交中击败了13.27% 的用户
思路2:顺序扫描,然后计数。代码如下:
class Solution { public: int search(vector & nums, int target) { int cnt = 0; for (const int i : nums) if (i == target) ++cnt; return cnt; }};
效率如下,因为有条件判断,可能出现分支预测失败:
执行用时:20 ms, 在所有 C++ 提交中击败了64.38% 的用户内存消耗:13.2 MB, 在所有 C++ 提交中击败了60.30% 的用户
思路3:二分找到最左边的值,然后顺序扫描到最右边的值。用 lower_bound
函数。这里不实现,复杂度和思路2一样。
思路4:二分找到最左边的值的位置,然后二分找到最右边的值的位置,就可以求出出现次数。使用STL的代码如下:
class Solution { public: int search(vector & nums, int target) { int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin(); return left >= right ? 0 : right - left; }};
手写二分如下:
class Solution { public: int lower(const vector &nums, int target) { int lo = 0, hi = nums.size(); while (lo < hi) { int mid = (lo + hi) / 2; if (nums[mid] >= target) hi = mid; else lo = mid + 1; } return lo; } int upper(const vector &nums, int target) { int lo = 0, hi = nums.size(); while (lo < hi) { int mid = (lo + hi) / 2; if (nums[mid] > target) hi = mid; else lo = mid + 1; } return lo; } int search(vector & nums, int target) { int left = lower(nums, target), right = upper(nums, target); return right - left; }};
转载地址:https://memcpy0.blog.csdn.net/article/details/108373461 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月17日 06时38分15秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
lambda表达式初探
2019-05-02
C++ Template类模板的特化(3.3节, 3.4节)
2019-05-02
第05章 函数
2019-05-02
第08章 输入和输出
2019-05-02
第11章 案例研究: 文本统计
2019-05-02
qml drag listview
2019-05-02
QT中文乱码的解
2019-05-02
netsh用法
2019-05-02
网上Qt多线程同步的一种普遍误识
2019-05-02
libcurl smtp发送邮件附件大小限制问题
2019-05-02
Qt中用QuaZip来压缩和解压缩文件
2019-05-02
第13章 Windows内存体系结构
2019-05-02
windows 和 linux 下c/c++内存分布(整理)
2019-05-02
Qt解析XML文件(QDomDocument)
2019-05-02
Qt图形视图框架
2019-05-02
Qt5中表格处理大数据量
2019-05-02
LeakCanary源码分析
2019-05-02
单例模式(Singleton)
2019-05-02
ucOS 时钟中断(ISR)
2019-05-02