更有效地分割重叠间隔，然后合并重复项 [英] More Efficient method to split overlapped intervals, then merge duplicates
本文介绍了更有效地分割重叠间隔，然后合并重复项的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
所以我正在尝试找出最有效的方法来拆分重叠的间隔，然后合并重复项。特定于我的情况的两个条件是，如果合并间隔的开始是原始间隔的结束，则加1。如果合并间隔的结束是原始间隔的开始，则减1。以下是一些样本数据和预期结果：
interface Interval {
start: number;
end: number;
type: Array<number>;
}
// starting data
const arr: Array<Interval> = [
{ start: 0, end: 16, type: [42] },
{ start: 6, end: 30, type: [95] },
{ start: 11, end: 24, type: [126] },
{ start: 32, end: 47, type: [42] }
].sort((a, b) => a.start - b.start);
// magic splitting code here
// what we expect to end up with
const end_arr: Array<Interval> = [
{ start: 0, end: 5, type: [42] },
{ start: 6, end: 10, type: [42, 95] },
{ start: 11, end: 16, type: [42, 95, 126] },
{ start: 17, end: 24, type: [95, 126] },
{ start: 25, end: 30, type: [95] },
{ start: 32, end: 47, type: [42] },
];
从技术上讲，我已经得到了这个问题的答案，但它的效率不是很高--涉及3个嵌套的for/forEach循环。当然还有更有效的办法吗？这是它的代码：
let startIndexArray: Array<number> = [];
let endIndexArray: Array<number> = [];
for (let i = 0; i < arr.length; i++) {
startIndexArray.push(arr[i].start);
endIndexArray.push(arr[i].end);
}
startIndexArray = startIndexArray.sort((a, b) => a - b);
endIndexArray = endIndexArray.sort((a, b) => a - b);
const indexArray = [...startIndexArray, ...endIndexArray].sort((a, b) => a - b);
const result: Array<Interval> = [];
arr.forEach((currentInterval) => {
for (let i = currentInterval.start; i < currentInterval.end; i++) {
if (indexArray.includes(i)) {
const position = indexArray.indexOf(i);
if (position !== indexArray.length - 1) {
let start = i;
let next = indexArray[position + 1];
if (endIndexArray.includes(start)) {
start = start + 1;
}
if (startIndexArray.includes(next)) {
next = next - 1;
}
let in_result = false;
result.forEach((mergedInterval) => {
if (mergedInterval.start === start && mergedInterval.end === next) {
mergedInterval.type = [...mergedInterval.type, ...currentInterval.type];
in_result = true;
}
});
if (!in_result) {
result.push({ start: start, end: next, type: [...currentInterval.type]});
}
}
}
}
});
// output is my expected, correct outcome
console.log(result);
推荐答案
以下算法是我所能想到的最干净的算法，具有合理的性能。我预计，对于您给出的特定示例数组，此代码和您上面给出的代码将具有相似的性能水平，但如果您开始使用更大的数组，您将在这里看到与您的相比的性能提升。如果没有一套测试用例，就很难确定。
不管怎样，大意是这样的。让我们调用一个Partition非重叠间隔的有序数组，它涵盖了从-Infinity到Infinity的所有整数。
type Partition = Array<Interval>;
Partition类型的值partition，我们知道partition[0].start === -Infinity，partition[partition.length-1].end === Infinity，对于任何索引i < partition.length - 1，partition[i].end + 1 === partition[i+1].start。
分区的一个好处是它始终只包含一个覆盖任何给定
position的间隔。这消除了一类边缘情况。因此，给定一个partition: Partition和一个position: number，让我们找出partition中包含它的区间的索引：
// binary search of the partition to find the index of the interval containing position
// startIndex is a hint, where partition[startIndex].start <= position
// endIndex is a hint, where partition[startIndex].end > position
function findIndex(
partition: Partition,
position: number,
startIndex: number = 0,
endIndex: number = partition.length
) {
while (true) {
let i = (startIndex + endIndex) >> 1;
let cur = partition[i];
if (cur.end <= position) {
startIndex = i;
} else if (cur.start > position) {
endIndex = i;
} else {
return i;
}
}
}
此算法是二进制搜索，如果您碰巧已经知道正确的间隔可能在分区中的什么位置，则它允许您向它提供有关开始和结束索引的提示。如果分区的长度为𝑛，则此算法应为𝖮(𝗅𝗈𝗀𝑛)。
另一个有用的操作是在特定的
position处拆分partition。如果分区已经包含从该位置开始的间隔，则无需执行任何操作。否则，您需要找到跨越该位置的间隔，并将其一分为二：
// ensure that the partition contains an interval starting at position
// startIndex is a hint, where partition[startIndex].start <= position
// return the index of the interval starting at position
function splitAt(partition: Partition, position: number, startIndex: number = 0) {
let i = findIndex(partition, position, startIndex);
let cur = partition[i];
if (cur.start < position) {
partition.splice(i, 1,
{ start: cur.start, end: position - 1, type: cur.type.slice() },
{ start: position, end: cur.end, type: cur.type }
)
i++;
}
return i;
}
此算法使用findIndex()，因此它也应该是𝖮(𝗅𝗈𝗀𝑛)。(编辑...我猜这取决于splice()，所以可能只有𝖮(𝑛))。
给定
partition: Partition和interval: Interval，我们如何将区间合并到分区中？我们需要在间隔的start位置和紧跟在间隔的end位置上拆分分区，然后遍历受影响的间隔并向其添加新间隔的type数组：
// merge interval into partition
function merge(partition: Partition, interval: Interval) {
// split partition at interval's start, get index of starting interval in partition
let startIndex = splitAt(partition, interval.start);
// split partition at interval's end, get index of interval after ending interval
let endIndex = splitAt(partition, interval.end + 1, startIndex);
// add types to each interval between start and end
for (let i = startIndex; i < endIndex; i++) {
partition[i].type.push(...interval.type);
}
}
这是一对二进制搜索加上遍历受影响的间隔。在最坏的情况下，分区中的每个间隔都需要修改，因此应该是𝖮(𝑛)。
最后，要将任意间隔数组转换为您想要的格式，只需从一个空的
Partition开始(它正好有一个从-Infinity到Infinity的间隔和一个空的type数组)，将每个间隔合并到其中，然后返回最终的Partition，而不返回type数组为空的任何间隔。这将自动取消接触Infinity或-Infinity的孔，以及中间的任何孔：
// denormalize array into non-overlapping intervals
function denormalize(arr: Array<Interval>) {
// empty partition
const partition: Partition = [{ start: -Infinity, end: Infinity, type: [] }];
arr.forEach(interval => merge(partition, interval));
// turn partition into normal array by removing "empty" intervals
return partition.filter(i => i.type.length !== 0);
}
merge()，因此在最坏的情况下，这将以𝖮(𝑛？)结束。我认为这可能是您对算法所能做的最好的事情；这意味着您不应该需要三个嵌套循环，但如果您能避免两个，我会很惊讶。
您可以验证它是否生成与您的版本相同的输出。可能存在边缘情况，但我对在
Partition上运行的算法更有信心，因为我不必一直问"如果我正在查看的位置没有与其关联的间隔怎么办？"？
备注：
您可能希望像
[start, end)中那样考虑让您的间隔半开。也就是说，start应该是该区间包含的最小位置，而end应该是大于的最小位置。半开音程更容易谱写和推理。[start, end)的长度为end - start。如果将间隔[a, b)和[b, c)合并，则得到[a, c)。如果您曾经决定需要从整数位切换到小数位，则半开区间不需要任何代码更改。相反，闭合区间需要仔细的数学运算才能在正确的位置加或减1(或不管步长是多少)，因此很容易出现栅栏柱错误。正如我前面所说，性能通常很重要，但它可能不如正确性那么重要。要确切知道性能对您的情况有多重要，唯一的方法是针对负载进行测试，并看看它的表现如何。通常，简单的算法比速度更快的复杂算法更可取，特别是如果您必须在将来维护和/或调试代码。
好的，希望这会有帮助；祝你好运！
这篇关于更有效地分割重叠间隔，然后合并重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
