如何使用NumPy对Nx2重叠整数对分组,合并为各组最小最大值数组
重叠配对的连通分组范围计算方案
核心实现逻辑:
- 该需求属于典型的传递连通性分组问题:只要两个配对存在任意共享端点,二者及所有间接关联的配对将被划为同一分组;最终每个分组输出组内所有数值的最小值、最大值组成的缩编配对。
- 采用并查集(DSU)结构实现全局关联的高效归集,避免嵌套遍历的性能损耗。
完整可运行代码:
import numpy as np class DSU: def __init__(self, size): self.root = list(range(size)) self.rank = [1] * size def find(self, x): if self.root[x] != x: self.root[x] = self.find(self.root[x]) return self.root[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.rank[x_root] > self.rank[y_root]: self.root[y_root] = x_root else: self.root[x_root] = y_root if self.rank[x_root] == self.rank[y_root]: self.rank[y_root] += 1 def compress_pairs(x): # 提取所有出现过的数值,建立值到连续索引的映射 all_vals = np.unique(x) val_to_idx = {v:i for i, v in enumerate(all_vals)} # 初始化并查集 dsu = DSU(len(all_vals)) # 对每个配对的两个数值执行关联合并 for a, b in x: dsu.union(val_to_idx[a], val_to_idx[b]) # 归集每个连通组的所有原始值 group_vals = {} for v in all_vals: root = dsu.find(val_to_idx[v]) group_vals.setdefault(root, []).append(v) # 每个组取最小值、最大值生成结果,按组最小值升序排列对齐示例输出 result = sorted( [[min(vals), max(vals)] for vals in group_vals.values()], key=lambda item: item[0] ) return np.array(result) # 题目示例输入测试 x = np.array([ [ 45, 47], [ 46, 47], [ 53, 54], [ 63, 66], [ 64, 66], [ 65, 66], [ 66, 67], [ 68, 70], [ 69, 70], [ 70, 71], [ 70, 72], [ 80, 81], [ 92, 93], [ 94, 95], [ 94, 96], [ 94, 97], [ 94, 98], [103, 104]]) print(compress_pairs(x))
代码运行输出与题目要求的期望结果完全一致:
[[ 45 47] [ 53 54] [ 63 67] [ 68 72] [ 80 81] [ 92 93] [ 94 98] [103 104]]
实现特性:
- 时间复杂度接近线性,支持十万级以上规模的配对输入快速计算
- 自动适配含负值、不连续值的输入场景,不依赖数值的连续性
- 最终结果按组最小值升序排列,匹配常规输出的阅读习惯
内容的提问来源于stack exchange,提问作者Estif
相关产品推荐
相关产品推荐

