Leetcode2336 无限集中的最小数字

news/2024/2/21 3:38:25

题目:

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类:

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
  • int popSmallest() 移除 并返回该无限集中的最小整数。
  • void addBack(int num) 如果正整数 num  存在于无限集中,则将一个 num 添加 到该无限集最后。

示例:

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 已经在集合中,所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ,并将其从集合中移除。
smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 在上一步中被添加到集合中,// 且 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ,并将其从集合中移除。

题目分析:

本题本质就是要实现两个操作:1、popSmallest() 2、addBack(num)。这里我们遇到第一个问题为什么初始化操作不用去实现。

解决这个问题要我们明确一个前提:无限集是无法实际在计算机中存储的。

所以对所谓无限集的操作仅仅是逻辑层面的,也就是说并不是创建一个真实的数组实际层面对数组对内层进行操作。而是逻辑上模拟内存的操作并进行输出结果。

接下来考虑如何实现pop和add操作:

pop操作:既然无限数组没有存在,那么我们仅仅需要模拟即可。所以就创建一个变量,记录目前弹出的无限集中的最大值的下一个。一开始指向1,1弹出后指向2,2弹出后指向3,如此循环。

add操作:由于上面的pop操作将无限集分为两个部分(分别是前面表示已经弹出的部分记为A,和后面未弹出的部分记为B),所以对于add操作,我们必然要考虑是add到哪一部分。如果是B部分,则不需要添加;如果是A部分,则需要添加进入数组,由于下次pop时必然是pop这里新加入的数所在的A部分中的最小数,所以这里要创建一个集合,用来存储add到A的数据。考虑到pop是弹出A中的最小值,所以要时刻保持集合中的数据有序,这里就采用set集合来保证。set集合内部维护采用的是堆排序。

当然分析到这里add会导致pop的方法改变。

图解分析:

代码如下: 

class SmallestInfiniteSet {
public:SmallestInfiniteSet() {}int popSmallest() {if (s.empty()) {int ans = thres;//thres就是分析中的t++thres;return ans;}int ans = *s.begin();s.erase(s.begin());return ans;}void addBack(int num) {if (num < thres) {s.insert(num);}}private:int thres = 1;set<int> s;//s就是分析中的a集合
};


https://www.xjx100.cn/news/3118977.html

相关文章

【STM32】OLED显示屏

1 调试方式 1. 串口调试&#xff1a;通过串口通信&#xff0c;将调试信息发送到电脑端&#xff0c;电脑使用串口助手显示调试信息 2. 显示屏调试&#xff1a;直接将显示屏连接到单片机&#xff0c;将调试信息打印在显示屏上 3. Keil调试模式&#xff1a;借助Keil软件的调试模…

一文秒懂|Linux字符设备驱动

我的圈子&#xff1a; 高级工程师聚集地 我是董哥&#xff0c;高级嵌入式软件开发工程师&#xff0c;从事嵌入式Linux驱动开发和系统开发&#xff0c;曾就职于世界500强公司&#xff01; 创作理念&#xff1a;专注分享高质量嵌入式文章&#xff0c;让大家读有所得&#xff01; …

制作心理咨询小程序的详细指南

随着科技的的发展&#xff0c;小程序已经成为了人们日常生活中不可或缺的一部分。特别是在心理咨询这个领域&#xff0c;小程序可以提供一个更为便捷、高效的服务平台。本文将通过乔拓云平台为例&#xff0c;详细介绍如何制作一个心理咨询小程序。 首先&#xff0c;我们需要注册…

c 语言常见的易错题分析

在C语言中&#xff0c;有一些常见的易错题需要特别注意。以下是一些例子&#xff1a; 1&#xff0c;数组越界&#xff1a;在C语言中&#xff0c;数组的索引是从0开始的。因此&#xff0c;一个长度为n的数组的索引范围应该是0到n-1。如果尝试访问超出这个范围的索引&#xff0c…

代码随想录 435. 无重叠区间

题目 给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。 示例 1: 输入: intervals [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后&#xff0c;剩下的区间没有重叠。 示…

【Openstack Train安装】五、Memcached/Etcd安装

本文介绍Memcached/Etcd安装步骤&#xff0c;Memcached/Etcd仅需在控制节点安装。 在按照本教程安装之前&#xff0c;请确保完成以下配置&#xff1a; 【Openstack Train安装】一、虚拟机创建 【Openstack Train安装】二、NTP安装 【Openstack Train安装】三、openstack安装…

让 OpenAI GPT4 出 10 道题测试其他开源大语言模型

让 OpenAI GPT4 出 10 道题测试其他开源大语言模型 1. 中文题目及答案2. 日文题目及答案3. 英文题目及答案 1. 中文题目及答案 数学题&#xff1a;一个矩形的长是10厘米&#xff0c;宽是5厘米&#xff0c;求它的面积。 答案&#xff1a;面积 长 x 宽 10厘米 x 5厘米 50平方厘…

YOLOv5原创改进:全维动态卷积再改进,GCODConv

目录 一、原理 网络结构 二、代码 三、应用到YOLOv5中 一、原理