如何保持列表不分段(阅读说明)

Question

我有以下问题（例如简化）

我有项目通过其ID 识别

class Item {
   private int id;
   public int getId(){
      return id;
   }
}

我想将它们保存在一个类中（让我们将其命名为ItemGroup），并满足以下条件：

• ItemGroup.getItems()应返回一个List<Item>（不需要按项目id排序的列表）
• 每次我向ItemGroup添加新项目时，它应该只维护具有更高且连续id的项目。一些例子可以更好地解释它：
  • 现有项=[5,6]，项ToAdd=[7,8]，结果=[5,6,7,8]
  • 现有项=[5，6]，项ToAdd=[8，9]，结果=[8。9]
  • 现有项=[5,6]，项ToAdd=[3,4]，结果=[3,4,5,6]
  • 现有项=[5,6]，项ToAdd=[1，2]，结果=[5,6

目标是实现聊天，在聊天中，消息以小数据包的形式从服务器恢复，主要要求线程拥有最后的消息，而没有碎片线程（缺少消息）。

例如，当客户端处于版本5，而服务器处于版本1000时，就会出现主要问题。客户端恢复最后10条找到ID（90-100]）项目的消息。在这种情况下，我想丢弃旧消息，允许用户向上滚动，如果需要，恢复以前的消息。

如何有效地实现这一点？我考虑过的选项是：

1. 使用List<Items>，每次添加新项目（或项目组）时运行Collections.sort（）。然后递减地迭代列表，当我检测到ID中的跳跃时，丢弃剩余的项目
2. 使用TreeSet，在修改集合后以相同的方式对列表进行碎片整理。方法getItems()返回一个new ArrayList<Item>(treeSet)
3. 使用List，每次需要插入项目时，通过二进制搜索查找正确的位置，在那里插入项目，然后对列表进行碎片整理。返回getItems()方法中未修改的列表
4. 更多解决方案

感谢

Answer 1

我不确定您的ID是否唯一，从我假设的示例来看，它们是唯一的。我还假设插入列表和主列表最初都有相应的元素如果是这样的话，算法就会很简单：

1. 插入前对两个列表进行排序
2. 比较插入列表中最低的（第一个）元素和主列表中最高的（最后一个）元素，如果相差1-插入到末尾，如果相差更多-替换主列表，返回
3. 比较插入列表中最高的元素和主列表中最低的元素，如果它们相差1，则插入开头；如果它们相差超过1，则丢弃插入的列表

该算法具有O（n）（用于值比较的O（1），用于元素插入的O（n。