查找范围数组中的重叠部分，并使用新的分块范围构建一个新数组

Find overlaps in array of ranges and build a new array with new chunked ranges

本文关键字：范围 数组 一个 新数组 构建 重叠部 查找      更新时间：2023-09-26

理想情况下，我想要Ruby或Javascript的解决方案。数组而不是javascript中的范围就可以了。

我想要输入，例如：

    [0..301, 230..268, 242..364, 574..579, 587..593]

或

    [0,301, 230,268, 242,364, 574,579, 587,593]

然后把它变成这样：

    [0..230, 230..242, 242..268, 268..301, 301..364, 574..579, 587..593]

或

    [[0,230], [230,242, [242,268], [268,301], [301,364], [574,579, [587,593]]

任何帮助都会很棒。这有点帮助，但并不完全是因为它给出了完整的范围，而不是分块的范围，我如何将整数数组汇总为范围数组？。

这里有一个ruby解决方案：

ranges = [0..301, 230..268, 242..364, 574..579, 587..593]
endpoints = ranges.map{|r| [r.first, r.last]}.flatten.sort
values = ranges.map{|r| r.to_a}.reduce(:+)
new_ranges = []
endpoints.reduce do |x, y|
    r = Range.new(x,y);
    new_ranges << r if r.all?{|v| values.include? v}
    y
end
puts new_ranges
#0..230
#230..242
#242..268
#268..301
#301..364
#574..579
#587..593

这里有一个Javascript解决方案：

(function (inp) {
    var out = [];
    inp.reduce(function (a,b) {
        return a.concat(b);
    }).sort().forEach(function(v,k, flat) {
        if(!k) return;
        out.push([flat[k-1], v]);
    });
    console.log(out);
})([[0,301], [230,268], [242,364], [574,579], [587,593]]);

此解决方案仅适用于支持Javascript 1.8的浏览器。我不得不调整您的输入以使其与Javascript兼容，因为正如jfriend00所说，Javascript没有范围。

这是输出：

[ [ 0, 230 ],
  [ 230, 242 ],
  [ 242, 268 ],
  [ 268, 301 ],
  [ 301, 364 ],
  [ 364, 574 ],
  [ 574, 579 ],
  [ 579, 587 ],
  [ 587, 593 ] ]

Ruby解决方案。

def f(a)
  a.map! {|r| [r.first, r.last ] }.sort!
  segs = [a.shift]
  a.each {|s, e|
    if segs.last.last < s
      segs << [s, e]
    else
      segs.last.concat [s, e]
      segs.last.sort!
    end
  }
  segs.map {|seg|
    seg.each_cons(2).map { |s, e| (s..e) }
  }.flatten
end
puts f([0..301, 230..268, 242..364, 574..579, 587..593])
#0..230
#230..242
#242..268
#268..301
#301..364
#574..579
#587..593
相关文章：