查找范围数组中的重叠,并用新的分块范围构建一个新数组
理想情况下,我想要一个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]]
任何帮助将是伟大的。这种帮助但不完全,因为它提供了全范围而不是分块范围,How do I summarize array of integers as an array of ranges?。
这里有一个红宝石的解决方案:
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
这是完美的!非常非常好的Ruby解决方案。 – phuphighter 2012-01-30 05:39:37
这里是一个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 ] ]
这看起来不像问题所要求的输出。 – jfriend00 2012-01-30 03:29:17
这非常接近,但不是我需要的100%。 – phuphighter 2012-01-30 03:35:39
@ jfriend00良好的通话。我解决了它。 – 2012-01-30 03:39:27
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
JavaScript没有像您指定的范围。你想要什么输入/输出格式,如果它的JavaScript? – jfriend00 2012-01-30 03:02:48
像[[0,230],[230,242] ...]这样的javascript数组就可以。我的坏,错过了。 – phuphighter 2012-01-30 03:23:16