javascript - 请教一个算法问题?

Question

请教一个算法问题

输入原数组(按start排序, 并且下一项的start一定>=前一项的end)

[    { "start": 1, "end": 2, "content": [ "A", "B", "E" ] },    //0    { "start": 2, "end": 3, "content": [ "B", "C" ] },        //1    { "start": 3, "end": 4, "content": [ "B", "D" ] },        //2    { "start": 4, "end": 5, "content": [ "D" ] },            //3    { "start": 7, "end": 8, "content": [ "B" ] },            //4    { "start": 9, "end": 11, "content": [ "B", "C" ] }        //5]

提取出连续的相同项合并成一个新的对象, 插入原数组, 根据start和end判断是否连续
如例子里的(0,1,2)项里的B 提取并合并得到{ "start": 1, "end": 4, "content": ["B"] }
(2,3)项里的D 提取并合并得到{ "start": 3, "end": 5, "content": ["D"] }
插入原数组后再按start, end 排序

提取后, (3)项会变为{ "start": 4, "end": 5, "content": [ ] }
content长度为0, 需要移除

最后输出

[    { "start": 1, "end": 2, "content": [ "A", "E" ] },    { "start": 1, "end": 4, "content": [ "B" ] },    { "start": 2, "end": 3, "content": [ "C" ] },    { "start": 3, "end": 5, "content": [ "D" ] },    { "start": 7, "end": 8, "content": [ "B" ] },    { "start": 9, "end": 11, "content": [ "B", "C" ] }]

Answer 1

function mergeSameItems(arr) {    let i = 0;    while (i < arr.length - 1) {        for (let j = 0; j < arr[i].content.length; j++) {            let item = arr[i].content[j];            if (arr[i + 1].content.includes(item)) {                arr.push({                    'start': arr[i].start,                    'end': arr[i + 1].end,                    'content': [item]                });                arr[i].content = arr[i].content.filter(x => x !== item);                arr[i + 1].content = arr[i + 1].content.filter(x => x !== item);            }        }        if (arr[i].content.length === 0) {            arr.splice(i, 1);        } else {            i += 1;        }    }    arr.sort((a, b) => a.start - b.start || a.end - b.end);    return arr;}

Answer 2

function merge(data) {    let obj1 = {}, obj2 = {};    for (let {start, end, content: arr} of data)        for (let key of arr)            (obj1[end] ??= {})[key] = [obj1[start]?.[key]?.pop() ?? start];    for (let [end, arr] of Object.entries(obj1))        for (let key in arr)            for (let start of arr[key])                (obj2[`${start},${end}`] ??= {start, end: +end, content: []}).content.push(key);    return Object.values(obj2).sort((a, b) => a.start - b.start || a.end - b.end);}

Answer 3

let arr = [    { "start": 1, "end": 2, "content": [ "A", "B", "E" ] },    //0    { "start": 2, "end": 3, "content": [ "B", "C" ] },        //1    { "start": 3, "end": 4, "content": [ "B", "D" ] },        //2    { "start": 4, "end": 5, "content": [ "D" ] },            //3    { "start": 7, "end": 8, "content": [ "B" ] },            //4    { "start": 9, "end": 11, "content": [ "B", "C" ] }        //5]let obj = {}let list = arr.reduce((list, item, index, arr) => {    item.content.forEach(citem => {        let i = index        let next, cindex        while ((next = arr[i + 1]) && arr[i].end === next.start && (cindex = next.content.indexOf(citem)) >= 0) {            i++            next.content.splice(cindex, 1)        }        let end = arr[i].end        let key = item.start + '-' + end        if(!obj[key]){            list.push(obj[key] = {                start: item.start,                end,                content: [citem]            })        }else{            obj[key].content.push(citem)        }    })    return list}, [])console.log(list)