如何在JavaScript中根据数组对象的关联重复值设置matched属性

需求说明 #

现有matchArray数组，每个元素为包含arr数组和matched布尔属性的对象。当前代码仅能将包含指定key值的对象的matched设为true，需实现：当多个对象的arr存在关联重复值时（如前三个对象的arr存在重叠数值），将这些关联对象的matched统一设为true，其余保持false。

原数组 #

let matchArray = [
    {
        "arr": [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34],
        "matched": false
    },
    {
        "arr": [ 33, 34, 35, 36, 37 ],
        "matched": false
    },
    {
        "arr": [ 36, 37, 38, 39, 40 ],
        "matched": false
    },
    {
        "arr": [ 42, 43 ],
        "matched": false
    },
    {
        "arr": [ 45, 46 ],
        "matched": false
    }
]

现有代码 #

const handleInputChangeForDay = (data) => {    
    const {value = '', key = 0} = data;

    setTrackArray(matchArray.map((item) => item.arr.includes(Number(key)) ? 
      {...item, matched: true} : item)
    );
}

期望输出 #

let matchArray = [
    {
        "arr": [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34],
        "matched": true
    },
    {
        "arr": [ 33, 34, 35, 36, 37 ],
        "matched": true
    },
    {
        "arr": [ 36, 37, 38, 39, 40 ],
        "matched": true
    },
    {
        "arr": [ 42, 43 ],
        "matched": false
    },
    {
        "arr": [ 45, 46 ],
        "matched": false
    }
]

解决方案 #

要实现关联元素批量标记，可通过**广度优先搜索（BFS）**找到所有与目标key关联的连通元素集合，再统一设置matched属性：

const handleInputChangeForDay = (data) => {    
    const {value = '', key = 0} = data;
    const targetKey = Number(key);

    // 将每个元素的arr转为Set，提升交集查询效率
    const elementSets = matchArray.map(item => new Set(item.arr));
    const visited = new Array(matchArray.length).fill(false);
    const queue = [];

    // 找到所有包含目标key的初始元素，加入BFS队列
    for (let i = 0; i < matchArray.length; i++) {
        if (elementSets[i].has(targetKey)) {
            visited[i] = true;
            queue.push(i);
        }
    }

    // BFS遍历所有关联元素
    while (queue.length > 0) {
        const currentIndex = queue.shift();
        const currentSet = elementSets[currentIndex];

        // 检查所有未访问元素，判断是否与当前元素存在数值重叠
        for (let i = 0; i < matchArray.length; i++) {
            if (!visited[i]) {
                const hasOverlap = [...elementSets[i]].some(num => currentSet.has(num));
                if (hasOverlap) {
                    visited[i] = true;
                    queue.push(i);
                }
            }
        }
    }

    // 根据访问标记更新matched属性
    const updatedArray = matchArray.map((item, index) => ({
        ...item,
        matched: visited[index]
    }));

    setTrackArray(updatedArray);
}

逻辑说明 #

1. 预处理：将每个元素的arr转换为Set，减少数值存在性查询的时间复杂度。
2. 初始化队列：找到所有包含目标key的元素，作为BFS的起始节点。
3. BFS遍历：从起始节点出发，逐个检查未访问元素是否与当前元素有数值重叠，若有则标记为已访问并加入队列，直到所有关联元素都被遍历。
4. 更新数组：根据访问标记，将所有关联元素的matched设为true，其余保持false。

内容的提问来源于stack exchange，提问作者Kamalesh Maity