工作中的一个问题之二

有一个二维数组如下：

let arr = [["a0", "a1"], ["a1", "a2"], ["a3"]];

我们看到 a1 这个元素在数组的第 0 项和第 1 项都存在了，我们需要将其合并成一项：

// 需要转化成 [["a0", "a1", "a2"], ["a3"]]

同理，针对一个任意项的二维数组，只要其中某单个元素重复了，就应该合并进同一个数组里，减少这个二维数组的个数。那么怎么实现这个呢？

闲话少叙，直接上代码。

第一种递归的方式

思路：找到出现了 2 次及以上的元素，记录他们出现的索引位置，用一个集合保存这些索引位置的元素；再合并没有合并过的其它索引位置的元素；递归这个过程，直到一个元素不再重复出现。

啊，语句很难表达这个意思出来，再看一次我自己都看不懂是什么意思了。还是仔细看代码吧。

这种方式由 liuqinh2s 提供算法支持。

function merge(arr) {
  let m = new Map();
  let needMerge = false;

  for (let i = 0; i < arr.length; i++) {
    for (const item of arr[i]) {
      let v = m.get(item) || [];
      v.push(i);
      m.set(item, v);

      if (v.length > 1) needMerge = true;
    }
  }

  if (!needMerge) return arr;

  let mergedArr = [];
  let mergedIndex = new Set();

  for (const [k, v] of m) {
    let s = new Set();
    if (v.length > 1) {
      for (const index of v) {
        if (!mergedIndex.has(index)) {
          for (const item of arr[index]) {
            s.add(item);
          }
          mergedIndex.add(index);
        }
      }
      if (s.size) {
        mergedArr.push([...s]);
      }
    }
  }

  for (let i = 0; i < arr.length; i++) {
    if (!mergedIndex.has(i)) mergedArr.push(arr[i]);
  }

  return merge(mergedArr);
}

let arr = [["a0", "a1"], ["a1", "a2"], ["a3"]];
// console.log(merge(arr));

let arr1 = [
  ["a4", "a5", "a7"],
  ["a2", "a3"],
  ["a0", "a1"],
  ["a1", "a2"],
  ["a3", "a4"],
  ["a5", "a6"],
  ["a9"],
];
// console.log(merge(arr1));

function randomData(length) {
  let arr = new Array(length);
  for (let i = 0; i < length; i++) {
    let count = ~~(Math.random() * length);
    let s = new Set();
    for (let j = 0; j < count; j++) {
      let char = String.fromCharCode(33 + j);
      s.add(char + ~~(Math.random() * length));
    }
    if (!s.size) s.add(-1);
    arr[i] = [...s];
  }

  return arr;
}

function merge2(arr) {
  let setArr = [];

  for (const item of arr) {
    let index = exists(item);
    let s;
    if (index === -1) {
      s = new Set();
      setArr.push(s);
    } else {
      s = setArr[index];
    }
    for (const ele of item) {
      s.add(ele);
    }
  }

  return [...setArr].map((_) => [..._]);

  function exists(arr) {
    let both = [];
    for (let i = 0; i < setArr.length; i++) {
      let s = setArr[i];
      for (const ele of arr) {
        if (s.has(ele)) !both.includes(i) && both.push(i);
      }
    }

    for (let i = both.length - 1; i > 0; i--) {
      let spliced = setArr.splice(both[i], 1);
      for (const item of spliced[0]) {
        setArr[both[0]].add(item);
      }
    }

    return both.length ? both[0] : -1;
  }
}

// console.log(merge2(arr));
// console.log(merge2(arr1));

let bigArr = randomData(100);
console.log(bigArr);

/*bigArr = [
[-1],
["!0", "\"0", "#2"],
["!1"],
["!4", "\"4"],
["!0", "\"4", "#2"]
]*/

console.time("recursion");
console.log(merge(bigArr));
console.timeEnd("recursion");

console.time("loop");
console.log(merge2(bigArr));
console.timeEnd("loop");

第二种遍历的方式

找到一个元素出现在集合数组中出现的所有索引位置，把这些位置上的集合合并，删掉已经合并的集合。有兴趣请详细看上述代码。

function merge2(arr) {
  let setArr = [];

  for (const item of arr) {
    let index = exists(item);
    let s;
    if (index === -1) {
      s = new Set();
      setArr.push(s);
    } else {
      s = setArr[index];
    }
    for (const ele of item) {
      s.add(ele);
    }
  }

  return [...setArr].map((_) => [..._]);

  function exists(arr) {
    let both = [];
    for (let i = 0; i < setArr.length; i++) {
      let s = setArr[i];
      for (const ele of arr) {
        if (s.has(ele)) !both.includes(i) && both.push(i);
      }
    }

    for (let i = both.length - 1; i > 0; i--) {
      // 昨天（2020-04-28）把 both[i] 写成了 i，出错了，调试了好久。
      let spliced = setArr.splice(both[i], 1);
      for (const item of spliced[0]) {
        setArr[both[0]].add(item);
      }
    }

    return both.length ? both[0] : -1;
  }
}

总结

• 递归是一种很有用的技巧，需要掌握。
• 但是递归一般是很慢的，拿这个例子来说，数据量越大慢得越明显。