对std::set使用lower_bound的效率问题

2023-05-16

1488题,洪水泛滥。在查找可用晴天时,如果使用 auto last_sunny_it = sunny.lower_bound(last_rain);就会超时。

而如果使用auto last_sunny_it = lower_bound(sunny.begin(),sunny.end(),last_rain); 就可以通过,性能较好。这2个lower_bound有什么差别吗?

vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n,1);
        unordered_map<int,int> pool2last_rain;
        set<int> sunny;
        for(int idx = 0;idx < n;idx++){
            if(rains[idx] == 0){
                sunny.insert(idx);
                continue;
            }
            if(pool2last_rain.count(rains[idx]) != 0){
                int last_rain = pool2last_rain[rains[idx]];
                auto last_sunny_it = lower_bound(sunny.begin(),sunny.end(),last_rain);
                //auto last_sunny_it = sunny.lower_bound(last_rain);
                if(last_sunny_it == sunny.end()) return {};
                int last_sunny_day = *last_sunny_it;
                sunny.erase(last_sunny_it);
                ans[last_sunny_day] = rains[idx];
            }
            pool2last_rain[rains[idx]] = idx;
            ans[idx] = -1;
        }
        return ans;
    }

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

对std::set使用lower_bound的效率问题 的相关文章

  • c++ max_element 每n个元素

    有没有办法比较每 N 个元素来找到容器中的最大元素并返回索引 使用 STL BOOST 或 其他库 对于每个 N 我的意思是使用 std max element 但将 for 的增加从 first 更改为 first n based on
  • 针对一组测试最小汉明距离的算法?

    我想做一件相对简单的事情 给定一个查询号码Q 查询距离d 和一组数字S 判断是否S包含any汉明距离小于或等于的数字d 最简单的解决方案就是使S一个列表并迭代它 计算距离 如果计算出的距离小于或等于 d 则退出返回TRUE 但考虑到我想做的
  • Coq 中 MSet 的使用示例

    MSets https coq inria fr library Coq MSets MSets html似乎是 OCaml 式有限集的最佳选择 可悲的是 我找不到示例用途 如何定义一个空的MSet或单身人士MSet 我怎样才能结合两个MS
  • 理解Python集合的行为

    内置类型的文档set says class set iterable 返回一个新的 set 或 freezeset 对象 其元素取自 可迭代的 集合的元素必须 可散列 没关系 但是为什么会这样 gt gt gt l range 10 gt
  • rdstate 和 rdbuf 中的 rd 代表什么?

    C 标准I O库中有两个名称 rdstate and rdbuf 我知道 state 和 buf 但是 rd 是什么 PS 我相信我知道如何使用rdstate and rdbuf 不要教我那个 我认为它们代表 read 类似于大多数人使用
  • Node JS,传统数据结构? (如 Set 等),类似于 Node 的 Java.util 之类的东西? [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我喜欢 Node JS 并且有 Java 背景 甚至有兴趣在某些 Node 看起来有点牵强的项目中尝试
  • 如何使用 set 维护列表的顺序?

    In 1 l1 a 2 3 0 9 0 0 2 6 b a In 2 l2 list set l1 In 3 l2 Out 3 a 0 2 3 6 9 0 b 在这里您可以看到列表 l2 的顺序与原始 l1 的顺序不同 我需要从列表中删除重
  • STL容器的范围插入函数在c ++ 11下返回void?

    刚刚学习c 所以我可能没有正确理解这一点 但我只读到范围插入函数在新标准下返回一个迭代器 C Primer 5th Ed cplusplus com http www cplusplus com reference string basic
  • Java 集合的添加、删除方法

    为什么该方法add
  • 删除元素时映射迭代器如何失效? [复制]

    这个问题在这里已经有答案了 使用擦除方法时 迭代器何时以及如何在映射中失效 例如 std map lt int int gt aMap aMap 33 1 aMap 42 10000 aMap 69 100 aMap 666 1 std m
  • 从 std::set 中提取仅移动类型

    我有一个std set
  • 在 C++ 中将数组转换为集合

    有没有更简单的方法使用 C 将数组转换为集合而不是循环遍历其元素 最好使用标准模板库 对于所有标准库容器类型 请使用构造函数 http en cppreference com w cpp container set set std set
  • 使用迭代器从“查找”或“删除”中删除

    我想知道在 C 中从向量中删除元素的最佳实践是什么 我多次看到人们使用 std remove 查找并删除元素 然后使用擦除从向量中删除元素 但为什么它比使用 find 获取要删除的元素的迭代器然后使用该迭代器的擦除更好呢 Thanks st
  • 如何对 HashSet 进行排序?

    对于列表 我们使用Collections sort List 方法 如果我们想对一个排序怎么办HashSet HashSet 不保证其元素的任何顺序 如果您需要这种保证 请考虑使用 TreeSet 来保存您的元素 但是 如果您只需要针对这一
  • 非不相交集并集的最佳算法是什么?

    假设有两个 非不相交 点集 笛卡尔空间 执行这两个集的并集的最佳情况复杂度算法是什么 由于点坐标是任意的 并且它们之间没有特殊关系 因此我不认为这个问题是一个几何特定问题 这是有效地将 S1 和 S2 合并成新集合 S 的通用问题 我知道有
  • set 中的哈希表在 python 中如何工作?

    据我所知 set在python中通过哈希表来实现O 1 查找复杂度 虽然它是哈希表 但其中的每个条目set必须是可散列的 或不可变的 所以这种和平的代码引发了异常 gt gt gt dict Traceback most recent ca
  • 将 uint64_t 转换为 std::string

    如何将 uint64 t 值传输到 std string 我需要构造包含该值的 std string 例如这样的事情 void genString uint64 t val std string str some code for str
  • 执行 set_difference 时出错:变量结果不是结构

    我在函数外部全局声明了一个设置变量 std set
  • 将 Set> 转换为 HashMap

    在我的代码中的某一时刻 我创建了一个Set
  • 值类型不完整的映射

    我收到以下错误 class Test std map

随机推荐

  • my cloud test bed (by quqi99)

    作者 张华 发表于 2023 03 10 版权声明 可以任意转载 转载时请务必以超链接形式标明文章原始出处和作者信息及本版权声明 问题 有一台NUC minipc 配置是 CPU i7 13700H 16核20线程 内存 16G 32G 4
  • try chatgpt api (by quqi99)

    作者 xff1a 张华 发表于 xff1a 2023 03 23 版权声明 xff1a 可以任意转载 xff0c 转载时请务必以超链接形式标明文章原始出处和作者信息及本版权声明 chatgpt web 试了网上的一个chatgpt web
  • ubuntu操音量调整命令amixer

    1 解除静音 sudo amixer set 39 Master 39 unmute sudo amixer set 39 Headphone 39 unmute sudo amixer set 39 Front 39 unmute 实际为
  • IAR软件应用中的错误提示

    1 Q xff1a Error e16 Segment XDATA Z size 0x19a1 align 0 is too long for segment definition At least 0xe4c more bytes nee
  • 软件工程—结构化分析设计

    进行完需求分析 xff0c 下一步该进行系统结构分析和设计了 现在主流的设计理念为结构化开发和面向对象开发 xff0c 本次主要讲解结构化开发 结构化开发分为结构化分析和设计两个阶段 结构化分析是面向数据流的分析方法 xff0c 基本思想是
  • 项目流标了怎么办?

    公开招标的项目如果出现流标现象 xff0c 是不能直接采取议标的方式 xff0c 或者直接采取竞争性谈判 单一来源采购 询价等非招标方式 xff0c 而应当组织二次招投标 xff0c 如果二次招标后仍然流标的 xff0c 可以核准后不再招标
  • xubuntu 14.04 LTS安装拼音输入法

    一 xff0c 安装fcitx sudo apt get install fcitx table wbpy 是不是很好记的样子 xff0c wb五笔py拼音 二 xff0c 配置fcitx desktop gnome language se
  • 整理库函数依赖关系

    问题 xff1a 现有一函数库 xff0c 这里是lapack3 5 lapack提供的每一个函数API都单独是一个 c 请给出这些API的相互调用关系 间接调用也要统计 xff0c 循环调用 xff08 如果可能的话 xff09 不计 进
  • 手把手教你写出正确的二分搜索!

    写出正确的二分搜索知易行难 xff0c 原理好像都懂 xff0c 但是实际上手就出各种错误 xff0c 例如如何确定循环终止条件 区间搜小判断条件等 这里就手把手教你写出正确的二分检索 xff01 二分法共有下面7种变式 是否存在数字t 返
  • SphereFace: Deep Hypersphere Embedding for Face Recognition

    Weiyang Liu 1 Yandong Wen 2 Zhiding Yu 2 Ming Li 3 Bhiksha Raj 2 Le Song 1 1 Georgia Institute of Technology 2 Carnegie
  • 一文解答你关于“轨道问题”的所有疑问!(有环链表问题)

    问题描述 xff1a 给定一个链表 xff0c 返回链表开始入环的第一个节点 如果链表无环 xff0c 则返回 NULL 我看过很多博客 xff0c 对于最优解法的解释无非两个字 xff0c 神奇 xff0c 并没有说明如何构思出这样的思路
  • 从bt到dp的困惑

    每一个dp的背后都必然有一个bt bt的基础上加上记忆化搜索 xff0c 然后对问题的拆分由从上到下变成从下到上 xff0c 即可转化为dp 但绝不是所有的bt就天然的可以转化为dp 例如下面这个例子 leetCode 115题 xff0c
  • 教练,我想学二叉树遍历!

    二叉树具有前序 中序 后序三种遍历方式 递归的相信大家都会写 xff0c 但是迭代的该怎么写呢 xff1f 怎样的迭代写法才能具有统一性便于理解呢 xff1f 请看下面具体的做法 xff0c 每种遍历方式各有2种策略 xff0c 基于栈的和
  • TVM优化原理学习

    没有看论文 xff0c 看了b站陈天奇的视频 xff0c 还有一些博客的分析 xff0c 学习了优化原理 后续需要深入理解再看论文 TVM对于神经网络的优化主要有两部分 xff0c 计算图优化和算子优化 xff0c 下面分开说明 计算图优化
  • 一个GDB调试的workflow

    我们要调试的程序是 include lt stdio h gt int main int p 61 NULL printf 34 p n 34 p p 61 3 printf 34 d n 34 p return 0 可以看到第6行会访问非
  • 记录一个很奇怪的bug,待解决

    一个很简单的矩阵求幂模板类的程序 xff0c 但是在vector lt vector lt T gt gt temp n vector lt T gt n 这一句不能执行 xff0c 会卡死 下面是完整的代码和输出 方阵的幂运算 xff0c
  • 听说还有人不懂右值和std::move()?

    1 左值和右值 左值是可以出现在等号左边的符号 xff0c 当然它也可以出现在等号右边 xff0c 例如int a等等 右值是能且只能出现在等号右边的符号 xff0c 例如5 xff0c abc 等等 右值细分为将亡值和纯右值 xff0c
  • 一个leetcode题目的bug记录【待解决】

    1403题目 xff0c 非递增顺序的最小子序列 题目很简单 xff0c 利用贪心的策略 xff0c 对数组从大到小排序 xff0c 然后尽量从前面取最小的满足题目要求的子数组即可 我的bug出在对数组从大到小排序这里 xff0c 报错代码
  • 字符串匹配KMP算法学习笔记

    字符串匹配 xff0c leetcode28题 时间复杂度O MN 的算法大家都会 xff0c 题解里面官方账号给出的利用字符串哈希判等的O N 算法也很优秀 本篇的重点是KMP算法 网上能搜到的KMP算法例子非常多 xff0c 其原理可以
  • 对std::set使用lower_bound的效率问题

    1488题 xff0c 洪水泛滥 在查找可用晴天时 xff0c 如果使用 auto last sunny it 61 sunny lower bound last rain 就会超时 而如果使用auto last sunny it 61 l