【数据结构和算法】无限集中的最小数字

绿毛龟

发布于 2024-01-19 11:00:02

20200

代码可运行

文章被收录于专栏：学习道路指南学习道路指南

运行总次数：0

代码可运行

前言

这是力扣的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 次

二、题解

这题的关键点是始终要保证无限集合是连续的。无限集合的范围可以认为是从 1 到正无穷大，并且都是正整数。

这道我是用TreeSet和一个min变量来维护这个无限集合。为什么用TreeSet，因为TreeSet支持维护元素的自然顺序。

TreeSet：小于min的有序集合。

min：有序集合的最小值。

添加元素的时候分为两种情况：

添加元素的时候如果添加的值大于等于无限集合中的最小值 min ，就不要添加，因为无限集合是连续的，添加的元素在无限集合中已经存在。（简单点说：比min还大的数不用加，说明已经存在了）
添加的元素如果小于无限集合的最小值 min 也不能直接添加，如果贸然添加会导致无限集合不连续，只需要把它添加到有序集合 TreeSet 中即可， TreeSet 中存放的值都是小于 min 的。所以要加在TreeSet中，要靠TreeSet来维护。

删除元素的时候：

删除的时候先判断有序集合 TreeSet 是否为空，如果不为空，说明存在比 min 还小的元素，直接从 TreeSet 中删除。否则就从有序集合中删除 min ，删除之后 min 值要加 1 。

三、代码

class SmallestInfiniteSet {
    TreeSet<Integer> set = new TreeSet<>();

    int min = 1;

    public SmallestInfiniteSet() {}

    public int popSmallest() {
        if (set.isEmpty()) {
            return min++;//先返回，再++
        }
        return set.pollFirst();//弹出set的第一个元素，并删除
    }

    public void addBack(int num) {
        if (num < min) {//大于的话，说明存在了
            set.add(num);
        }
    }
}

四、总结

使用TreeSet和min变量来维护一个无限集合，保证集合的连续性。添加元素时，若元素大于等于min，则不添加；若元素小于min，则将其添加到TreeSet中。删除元素时，先判断TreeSet是否为空，若不为空，则从TreeSet中删除元素；若为空，则将min值加1。该算法能够高效地添加和删除元素，并保持集合的连续性。

该算法还可以用优先队列（小根堆）+ hash表解题，比较优秀。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

变量