用近距离Javascript替换多维数组

Question

假设我们有一个范围列表，用两个元素[from, to]的数组表示。

当我们添加像[5,8]这样的新数组范围时，它应该在List中检查是否有最近的范围，然后用新的范围值替换它。下面提供了一个示例：

示例1

var List = [[1,2], [3,4], [6,7], [9,10]]
var newData = [5,8]

预期输出：

[[1,2], [3,4], [5,8], [9,10]]

[6,7]范围已包含在[5,8]中

示例2

var List = [[1,3], [4,6], [8,10]]
var newData = [5,9]

预期输出：

[[1,3], [4,10]]

Answer 1

假设初始列表格式良好，对已排序且不重叠，则可以使用二进制搜索来查找数组中新对的端点，从而确定任何重叠。如果重叠，则相应地拼接阵列：

function addSegments(segments, ...pairs) {
for (let pair of pairs) {
let [start, end] = pair.map(function (x, i) { // Binary search
let low = 0, 
high = segments.length;
side = 1 - i;
while (low < high) {
let mid = (low + high) >> 1;
if (x < segments[mid][side]) high = mid;
else low = mid + 1;
}
return low - (side && segments[low-1]?.[side] === x);
});
if (start < end) {
pair = [
Math.min(segments[start][0], pair[0]),
Math.max(segments[end-1][1], pair[1])
];
}
segments.splice(start, end - start, pair);
}
}
// Demo
let list = [[1, 2], [3, 4], [6, 7], [9, 10]];
addSegments(list, [5, 8]);
console.log(JSON.stringify(list));
list = [[1, 3], [4, 6], [8, 10]];
addSegments(list, [5, 9]);
console.log(JSON.stringify(list));

Answer 2

如果我们有两个数组，其中包含范围中包含的所有整数，那么我们可以相交并查看它们是否重叠。如果他们这样做了，我们将从两个范围的并集创建一个新的范围，并在输出中使用它。

为此，我们定义了三个辅助函数，range()、intersect()和union()，然后用它们来生成输出数组。如果存在交集，我们用两者的新并集覆盖任何重叠的范围。我假设，如果两个范围刚刚接触，它们就不应该组合在一起，所以只有当交集包含多个元素时才会触发覆盖。此外，我添加了一个初始排序。

function add(list, data) {

let buffer = [], idx;
const range=(a,b)=>Array.from({length:b-a+1}, (_, i)=>(a+i));
const intersect=(a,b)=>a.filter(x=>b.includes(x));
const union=(a,b)=>[...new Set([...a, ...b])].sort((a,b)=>a-b);
list.sort((a,b)=>a[0]-b[0]);

list.forEach(el=>{

let x = range(el[0], el[1]);
let y = range(data[0], data[1]);
let i = intersect(x, y);

if(i.length>1) {
let d = union(x,y);
data = [d[0], d[d.length-1]];
if(idx) { buffer[idx] = data; }
else { idx = buffer.push(data)-1; }
} 
else { buffer.push(el); };

});

return buffer;

}

// DEMO
let List = [[1,2], [3,4], [6,7], [9,10]];
let newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');
List = [[1,3], [4,6], [8,10]];
newData = [5,9];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');
// DEMO WITH UNORDERED ELEMENTS
List = [[3,4], [9,10], [6,7], [1,2]];
newData = [5,8];
console.log(JSON.stringify(List));
console.log(JSON.stringify(newData));
console.log(JSON.stringify(add(List, newData)));
console.log('');