### 高效管理离散值和连续区间的自定义数据类型 在 Python 中，设计一个能够高效管理包含离散值和连续区间的自定义数据类型的方案，需综合考虑以下几个方面：存储结构的选择、增删改查的操作实现以及快速判断数值是否属于该数据类型的能力。 #### 1. **存储结构** 推荐采用基于集合（`set`）和有序列表（`sortedcontainers.SortedList` 或 `bisect` 模块辅助的普通列表）相结合的方式来分别存储离散值和连续区间。具体原因如下： - 使用集合（`set`）存储离散值可以保证 O(1) 时间复杂度下的查找、插入和删除操作[^4]。 - 对于连续区间，由于需要支持高效的范围查询，建议使用有序列表配合二分查找算法来加速操作。这可以通过引入第三方库 `sortedcontainers` 实现，或者手动借助标准库中的 `bisect` 完成[^5]。 #### 2. **类封装与功能实现** 以下是一个完整的类设计方案，涵盖了增删改查及快速判断的功能： ```python from sortedcontainers import SortedList class IntervalSet: def __init__(self): self.discrete_values = set() # 存储离散值 self.intervals = SortedList() # 存储连续区间，格式为 (start, end)，保持升序排列 def _merge_intervals(self): """ 合并重叠或相邻的区间 """ merged = [] for interval in self.intervals: if not merged or merged[-1][1] < interval[0] - 1: merged.append(interval) else: merged[-1] = (merged[-1][0], max(merged[-1][1], interval[1])) self.intervals.clear() self.intervals.update(merged) def add_discrete(self, value): """ 添加单个离散值 """ self.discrete_values.add(value) def remove_discrete(self, value): """ 删除单个离散值 """ self.discrete_values.discard(value) def add_interval(self, start, end): """ 添加一个新的连续区间，并自动合并可能存在的重叠部分 """ if start > end: raise ValueError("Invalid interval: start must be less than or equal to end.") self.intervals.add((start, end)) self._merge_intervals() def remove_interval(self, start, end): """ 移除指定范围内覆盖的部分区间 """ new_intervals = [] i = 0 while i < len(self.intervals): current_start, current_end = self.intervals[i] if current_end < start or current_start > end: new_intervals.append((current_start, current_end)) elif current_start >= start and current_end <= end: pass # 整个区间被移除 else: if current_start < start: new_intervals.append((current_start, start - 1)) if current_end > end: new_intervals.append((end + 1, current_end)) i += 1 self.intervals.clear() self.intervals.update(new_intervals) self._merge_intervals() def update_discrete(self, old_value, new_value): """ 更新离散值 """ if old_value in self.discrete_values: self.remove_discrete(old_value) self.add_discrete(new_value) def contains(self, value): """ 判断某个值是否属于当前数据类型 """ if value in self.discrete_values: return True pos = self.intervals.bisect_left((value, value)) if pos != len(self.intervals) and self.intervals[pos][0] <= value <= self.intervals[pos][1]: return True if pos > 0 and self.intervals[pos - 1][0] <= value <= self.intervals[pos - 1][1]: return True return False # 示例用法 interval_set = IntervalSet() interval_set.add_discrete(1) interval_set.add_discrete(7) interval_set.add_interval(3, 5) interval_set.add_interval(8, 10) print(interval_set.contains(1)) # 输出: True print(interval_set.contains(4)) # 输出: True print(interval_set.contains(6)) # 输出: False print(interval_set.contains(9)) # 输出: True ``` --- ### 功能解析 1. **离散值管理** - 离散值通过集合（`set`）进行存储，因此其增删改查均具有较高的时间效率[^4]。 2. **连续区间管理** - 连续区间存放在有序列表中，便于执行二分查找以提升性能。新增加或修改区间时会触发 `_merge_intervals()` 方法，确保不会存在重复或交叉的区间[^5]。 3. **快速判断归属** - 调用 `contains()` 函数即可迅速判定目标值是否位于任何已知的离散值或连续区间内。此过程充分利用了集合特性和二分查找技术，整体运行速度较快[^6]。 --- ###