You need to enable JavaScript to run this app. 如何使用NumPy对Nx2重叠整数对分组,合并为各组最小最大值数组
优惠活动
大模型
产品
解决方案
定价
更多

如何使用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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.14 02:36:07