LeetCode:2336. 无限集中的最小数字(hash模拟 C++)

news/2024/2/29 4:19:23

目录

2336. 无限集中的最小数字

题目描述:

实现代码与解析:

set

原理思路:

优先级队列


2336. 无限集中的最小数字

题目描述:

        现有一个包含所有正整数的集合 [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 <= num <= 1000
  • 最多调用 popSmallest 和 addBack 方法 共计 1000 次

实现代码与解析:

set

class SmallestInfiniteSet {
public:set<int> s;int m = 1; // 记录最小值SmallestInfiniteSet() {}int popSmallest() {int res = 0;if (s.empty()) {res = m++;} else {res = *s.begin();s.erase(s.begin());}return res;}void addBack(int num) {if (num < m) {s.insert(num);}}
};
class SmallestInfiniteSet {private TreeSet<Integer> set;private int m = 1;public SmallestInfiniteSet() {set = new TreeSet<Integer>();}public int popSmallest() {return set.isEmpty() ? m++ : set.pollFirst();}public void addBack(int num) {if (num < m) set.add(num);}
}

原理思路:

        m 来表示在12345....序列中还没有pop出的最小值,set用来存放新add并且小于m的值,毕竟大于m的值已经存在且未pop出,在popSmallest函数中,若set为空,说明最小值为m,不为空,说明add的数有小于m的,返回set的第一个数。当然,很显然,这题用优先级队列也是可以写的。

        不过要注意,优先级队列不能去重,添加的数可能已经存在与队列,所以要多一个数组来判断一下。

优先级队列

class SmallestInfiniteSet {
public:priority_queue<int, vector<int>, greater<int>> q;int m = 1; // 记录最小值vector<bool> d = vector<bool> (1010, false);SmallestInfiniteSet() {}int popSmallest() {int res = 0;if (q.empty()) {res = m++;} else {res = q.top();q.pop();d[res] = false;}return res;}void addBack(int num) {if (num < m && !d[num]) {q.push(num);d[num] = true;;}}
};

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

相关文章

用python求出1-100的和(6种方式)

求1到100数字的合计 #方法一 sum20 for i in range(1,101):sum2i print("---sum1---") print(sum2)#方法二 def fsum(n):s0for i in range(1,n1):siprint(s) print("----sum2----") fsum(100)#方法三while循环实现 def fsum1(n):i0 #初始化变量s0while i …

RK3568平台开发系列讲解(Linux系统篇)通过OF函数获取设备树节点实验

** 🚀返回专栏总目录 文章目录 一、获取获取设备树节点二、驱动程序沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍通过OF函数获取设备树节点实验 一、获取获取设备树节点 在 Linux 内核源码中提供了一系列的 of 操作函数来帮助我们获取到设备树中编写的…

BeanUtil.copyProperties的优化与使用(解决copyProperties null值覆盖问题)

BeanUtil.copyProperties的优化与使用 前言一、copyProperties是什么&#xff1f;二、使用步骤1.引入库2.基础使用3.进阶使用4.实用场景 总结 前言 BeanUtil.copyProperties的优化与使用 一、copyProperties是什么&#xff1f; 在java中&#xff0c;我们想要将一个类的值赋值…

React 签字手写签名组件 react-signature

安装依赖包 npm install uiw/react-signature示例代码 import React, { useRef } from "react"; import Signature from uiw/react-signature;export default function App() {const $svg useRef(null);const handle (evn) > $svg.current?.clear();return (…

uniapp开发小程序使用axios进行网络请求 uniapp 小程序调试

前言 本篇最好放到项目的【README.md】文件中,方便每次发布的时候检查纠错,毕竟好记性不如烂笔头。而且其他开发者帮忙修改bug、发布新版本的时候,只需要根据这个事项就能实现整个流程的提审发布,提高效率。 1、微信小程序配置 1.1、检查APPID是否正确 测试:wx--------…

第八天:信息打点-系统端口CDN负载均衡防火墙

信息打点-系统篇&端口扫描&CDN服务&负载均衡&WAF防火墙 一、知识点 1、获取网络信息-服务器厂商&#xff1a; 阿里云&#xff0c;腾讯云&#xff0c;机房内部等。 网络架构&#xff1a; 内外网环境。 2、获取服务信息-应用协议-内网资产&#xff1a; FTP…

OpenHarmony 4.0 Release 编译及报错

1、环境准备 安装下面这三东西&#xff0c;是为了下载 Harmony 源码 sudo apt install curl sudo apt install python3-pip sudo apt install git-lfs 安装下面这五个东西&#xff0c;是为了解决编译到最后报错(头铁不信的&#xff0c;你可以试试&#xff0c;等最后再安装) …

Web实现悬浮球-可点击拖拽禁止区域

这次要实现的是这种效果&#xff0c;能够在页面上推拽和点击的&#xff0c;拖拽的话&#xff0c;就跟随鼠标移动&#xff0c;点击的话&#xff0c;就触发新的行为&#xff0c;当然也有指定某些区域不能拖拽&#xff0c;接下来就一起来看看有什么难点吧~ 需要监听的鼠标事件 既…