合并数组并保持排序

Question

笔记

该问题已根据 @Kaddath 的好建议进行了编辑，以强调排序不必按字母顺序排列，而是取决于数组内项目的位置。

---

我有一个数组数组，其中每个数组都基于给定的顺序，但它们可能略有不同。

例如，基本排序是X -> D -> H -> B，这是我的数组：

const arrays = [
  ['X', 'D', 'H', 'B'],
  ['X', 'D', 'K', 'Z', 'H', 'B', 'A'],
  ['X', 'M', 'D', 'H', 'B'],
  ['X', 'H', 'T'],
  ['X', 'D', 'H', 'B']
]

我想将所有数组合并为一个数组并删除重复项，但保持排序。在我的示例中，结果将是['X', 'M', 'D', 'K', 'Z', 'H', 'T', 'B', 'A'].

在示例中，我们可以看到M位于第三个数组之间X和内部，并且它被放置在最终输出中和之间。DXD

我知道可能会出现冲突，但这里有以下规则：

• 每个项目都应该出现在最终输出中。
• 如果一个项目出现在多个数组的不同位置，则第一个出现的就是正确的（跳过其他）。

到目前为止我所做的是将所有这些数组合并为一个数组，方法是使用

const merged = [].concat.apply([], arrays);

（参见/sf/answers/760552971/）。

然后使用/sf/answers/110906421/中的代码片段获取唯一值：

Array.prototype.unique = function() {
    var a = this.concat();
    for(var i=0; i<a.length; ++i) {
        for(var j=i+1; j<a.length; ++j) {
            if(a[i] === a[j])
                a.splice(j--, 1);
        }
    }

    return a;
}; 
const finalArray = merged.unique();

但我的结果是这样的：

[
  "X",
  "D",
  "H",
  "B",
  "K",
  "Z",
  "A",
  "M",
  "T"
]

欢迎任何帮助！

谢谢。

Answer 1

每个数组实际上都是一组规则，用于说明元素之间的相对顺序。最终列表应返回所有元素，同时遵守所有规则定义的相对顺序。

有些解决方案已经解决了最初的请求，有些甚至没有解决这个问题（所有建议使用排序的方法都错过了问题的要点）。然而，没有人提出通用的解决方案。

问题

如果我们看一下OP中提出的问题，规则就是这样定义元素之间的相对位置的：

   M    K -> Z    T
  ^ \  ^      \  ^
 /   v/        v/
X -> D ------> H -> B -> A

因此，很容易看出我们的数组以 X 开头。下一个元素可以是 D 和 M。但是，D 要求 M 已经在数组中。这就是为什么我们将M作为下一个元素，然后是D。接下来，D同时指向K和H。但是由于H还有一些其他的前驱元素到目前为止还没有收集到，而K没有（实际上它有D，但它已经收集在列表中），我们将放入 K 和 Z，然后才放入 H。

H同时指向T和B。实际上我们把哪一个放在前面并不重要。因此，最后三个元素可以采用以下三个顺序中的任何一个：

• 乙、乙、甲
• 乙、甲、乙
• 乙、乙、乙

让我们还考虑一下更复杂的情况。规则如下：

['10', '11', '12', '1', '2'],
['11', '12', '13', '2'],
['9', '13'],
['9', '10'],

如果我们使用这些规则绘制图表，我们将得到以下结果：

   --------------> 13 ----
  /                ^      \
 /                /        v
9 -> 10 -> 11 -> 12 > 1 -> 2

本案有何具体情况？两件事情：

• 只有在最后一条规则中我们“发现”数字 9 是数组的开头
• 从 12 到 2 有两条非直接路径（一条经过数字 1，第二条经过数字 13）。

解决方案

我的想法是从每个元素创建一个节点。然后使用该节点来跟踪所有直接后继者和直接前驱者。之后，我们将找到所有没有前驱的元素并开始从那里“收集”结果。如果我们到达有多个前驱的节点，但其中一些没有被收集，我们将在那里停止递归。可能会发生一些后继者已经在其他路径中收集的情况。我们会跳过那个继任者。

   M    K -> Z    T
  ^ \  ^      \  ^
 /   v/        v/
X -> D ------> H -> B -> A

大O

如果我们说n是规则的数量，m是每个规则中元素的数量，则该算法的复杂度为O(n*m)。这考虑到JS 的 Set 实现接近 O(1)。

Answer 2

const arrays = [
  ['X', 'D', 'H', 'B'],
  ['X', 'D', 'K', 'Z', 'H', 'B', 'A'],
  ['X', 'M', 'D', 'H', 'B'],
  ['X', 'H', 'T'],
  ['X', 'D', 'H', 'B']
];
const result = [];
arrays.forEach(array => {
  array.forEach((item, idx) => {
    // check if the item has already been added, if not, try to add
    if(!~result.indexOf(item)) {
      // if item is not first item, find position of his left sibling in result array
      if(idx) {
        const result_idx = result.indexOf(array[idx - 1]);
        // add item after left sibling position
        result.splice(result_idx + 1, 0, item);
        return;
      }
      result.push(item);
    }
  });
});
console.log('expected result', ['X', 'M', 'D', 'K', 'Z', 'H', 'T', 'B', 'A'].join(','));
console.log(' current result',result.join(','));