当前位置: 首页 > news >正文

管理系统 网站模板信息流优化师培训

管理系统 网站模板,信息流优化师培训,网站建设售后服务合同,优秀品牌网站案例分析题目: 有 n 个 (id, value) 对,其中 id 是 1 到 n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。 设计一个流,以 任意 顺序获取 n 个 (id, value) 对,并在多次调用时 按 id 递增的顺序…

题目:

有 n 个 (id, value) 对,其中 id 是 1 到 n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流,以 任意 顺序获取 n 个 (id, value) 对,并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类:

  • OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针 ptr 设为 1 。
  • String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后:
    • 如果流存储有 id = ptr 的 (id, value) 对,则找出从 id = ptr 开始的 最长 id 连续递增序列 ,并 按顺序 返回与这些 id 关联的值的列表。然后,将 ptr 更新为最后那个  id + 1 。
    • 否则,返回一个空列表。

示例:

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc"),返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa"),返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb"),返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee"),返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd"),返回 ["ddddd", "eeeee"]

提示:

  • 1 <= n <= 1000
  • 1 <= id <= n
  • value.length == 5
  • value 仅由小写字母组成
  • 每次调用 insert 都会使用一个唯一的 id
  • 恰好调用 n 次 insert

解法:基于数组和指针的流式处理

解题思路

我们需要设计一个数据结构,能够按 id 递增的顺序返回 (id, value) 对的值。由于 id 是唯一的且范围固定(1 到 n),我们可以使用一个数组来存储这些值,并通过一个指针 ptr 来跟踪当前可以返回的最小 id

具体步骤如下:

  1. 初始化

    • 使用一个大小为 n + 1 的数组 stream 来存储 (id, value) 对。数组的索引直接对应 id,方便快速访问。

    • 初始化指针 ptr 为 1,表示下一个需要返回的 id 是 1

  2. 插入操作

    • 将 (idKey, value) 对存储到数组 stream 的 idKey 位置。

    • 检查当前指针 ptr 是否指向一个已经存储了值的 id。如果是,则从 ptr 开始,依次检查连续的 id 是否已经存储,并将对应的 value 加入结果列表。

    • 更新指针 ptr 为最后一个连续 id 的下一个位置。

    • 返回结果列表。

代码实现

class OrderedStream {
private:vector<string> stream;  // 用于存储 (id, value) 对的数组int ptr;                // 当前指针,指向下一个应该返回的 idpublic:OrderedStream(int n) {stream.resize(n+1);ptr = 1;}vector<string> insert(int idKey, string value) {stream[idKey] = value;vector<string> result;// 如果当前指针指向的 id 已经存储了值,则返回从 ptr 开始的最长连续递增序列while (ptr < stream.size() && !stream[ptr].empty()) {result.push_back(stream[ptr]);ptr++;}return result;}
};/*** Your OrderedStream object will be instantiated and called as such:* OrderedStream* obj = new OrderedStream(n);* vector<string> param_1 = obj->insert(idKey,value);*/

复杂度分析

  1. 时间复杂度

    • 每次调用 insert 方法时,最坏情况下需要遍历从 ptr 开始的所有连续 id,时间复杂度为 O(k),其中 k 是连续 id 的数量。

    • 总体时间复杂度为 O(n),因为每个 id 最多被遍历一次。

  2. 空间复杂度

    • 使用了一个大小为 n + 1 的数组来存储 (id, value) 对,空间复杂度为 O(n)

示例运行

以下是对示例的运行过程分析:

  1. 初始化 OrderedStream(5)stream 数组大小为 6ptr = 1

  2. 调用 insert(3, "cc")

    • 存储 stream[3] = "cc"

    • ptr = 1stream[1] 为空,返回 []

  3. 调用 insert(1, "aa")

    • 存储 stream[1] = "aa"

    • ptr = 1stream[1] 不为空,返回 ["aa"]ptr 更新为 2

  4. 调用 insert(2, "bb")

    • 存储 stream[2] = "bb"

    • ptr = 2stream[2] 不为空,返回 ["bb"]ptr 更新为 3

  5. 调用 insert(5, "ee")

    • 存储 stream[5] = "ee"

    • ptr = 3stream[3] 不为空,返回 ["cc"]ptr 更新为 4

  6. 调用 insert(4, "dd")

    • 存储 stream[4] = "dd"

    • ptr = 4stream[4] 不为空,返回 ["dd", "ee"]ptr 更新为 6

总结

通过使用数组和指针,我们可以高效地实现按 id 递增顺序返回值的功能。该方法的时间复杂度和空间复杂度均为 O(n),能够很好地处理流式数据。

http://www.tj-hxxt.cn/news/23743.html

相关文章:

  • 齐鲁人才网seo优化教程下载
  • 茶叶淘宝店网站建设pptseo搜索引擎优化课程
  • 重庆市建设城乡委员会官方网站初学seo网站推广需要怎么做
  • 如何使用花生壳做网站搜索引擎优化课程总结
  • 我想采集散文 做网站哈尔滨网站优化流程
  • 做热点图现在用什么网站百度秒收录软件
  • 淄博高端网站建设乐达世界杯排名
  • 湖南专业网站建设服务seo快速优化排名
  • 做网站用什么cms 知乎网站seo具体怎么做?
  • 学做网站设计全网关键词搜索
  • 网站怎么做前后台存取抖音seo怎么做的
  • 海南网站建设网站开发不收费的小说网站排名
  • 双鸭山seo保定seo排名优化
  • 专业做网站团队个人网页设计
  • 苏州网站优化公司产品市场营销策划书
  • 重庆网络技术有限公司广告优化师工资一般多少
  • 网站规划与建设是什么意思黑龙seo网站优化
  • 高端网站制作建设艾瑞指数
  • 电子商务网站建设教程百度站长工具seo查询
  • 苏州做网站哪家好抖音矩阵排名软件seo
  • ps做好的网站如何做链接谷歌平台推广外贸
  • wordpress后台经常504南京广告宣传公司seo
  • 做网站赚钱吗是真的吗天眼查企业查询入口
  • 招聘网站建设规划书想做百度推广找谁
  • 网站如何做熊掌号并绑定广州seo工资
  • 网站开发分几种类型肇庆网站推广排名
  • 织梦做的网站今日百度搜索风云榜
  • 电子商务 网站建设360关键词排名百度
  • 找人做网站去哪里找如何联系百度人工客服电话
  • 设计灵感网站整理青岛建站seo公司