请教一个查重的算法

Question

存在若干个对象

[
  { name: 'a', set: [1, 2, 3] },
  { name: 'b', set: [2, 3, 4] },
  { name: 'c', set: [1, 2, 4] }
]

查找 set 中跟其他对象的 set 存在重复的元素后返回 name 的集合（数组），请教各位！！感谢！

Answer 1

const arr = [...]
const bucket = []
for (const obj of arr) {
    for (const n of obj.set) {
        bucket[n] ??= 0
        bucket[n] ++
    }
}
const dupNames = arr
    .filter(obj => obj.set.some(n => bucket[n] > 1))
    .map(obj => obj.name)

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 2

先对每个元素计数，再来根据当前对象判断计数是否大于 1（如果等 1 说明是它自己），@ForkKILLET 这是个很容易懂的方法

const map = data.flatMap(({ set }) => set)
    .reduce((acc, v) => (acc[v] = (acc[v] ??= 0) + 1, acc), {});
console.log(map);

const result = data
    .filter(({ set }) => set.some(v => map[v] > 1))
    .map(({ name }) => name);

另外一种方法，采用指针位移的方法来处理，把找到重合的往前放，并计数，根据计数来取前 n 个就是

// hasRepest 用来检查两个数组是否有交集，即是否存在重合元素
const hasRepeat = (a, b) => a.some(v => b.includes(v));

// 用一个临时变量来引用数组元素，因为要改变它
const cache = [...data];
// 记录已经找到的重复数
let count = 0;

// 两重循环，因为 count 表示已经找到重复的，
// 所以从 count 数的下一个开始找，也就是索引号为 count 的那个
for (let i = 0; i < data.length - 1; i = count) {
    // 一开始 cache[i] 肯定是不重复的，
    // 但是发现重复，它需要计数，但不管重复多少次，只计数 1 次，所以需要一个标志
    let iIs = false;

    // 从 i 元素的下一个开始比较
    for (let j = i + 1; j < data.length; j++) {
        // 未重合拉倒。如果重合，需要把 j 元素计数，同时把它的位置交换到前面去
        if (hasRepeat(cache[i].set, cache[j].set)) {
            // 如果 i 元素未计数，则计数
            if (!iIs) {
                count++;
                iIs = true;
            }
            // 因为 j 元素是新找到的，所以放在之前找到的之后，也就是 count 所指的位置
            [cache[count], cache[j]] = [cache[j], cache[count]];
            // 然后把它算到 count 里去
            count++;
        }
    }
}

const result = cache.slice(0, count).map(({ name }) => name);

这个方法处理起来要复杂一些，而且没验证其正确性，仅供参考。

---

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。