合并数组并保持顺序

Question

合并数组并保持顺序

javascriptarraystopological-sort

6

注意

根据 @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和D之间，最终输出中也是这样。

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

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

到目前为止我所做的是使用

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

参考：https://dev59.com/cmgv5IYBdhLWcg3wD8yY#10865042。

然后，使用此代码片段从https://dev59.com/BHI-5IYBdhLWcg3w-9wK#1584377获取唯一值：

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"
]

任何帮助都受欢迎！感谢。

- MHogge

1

合并后不能对数组进行排序吗？ - Jerodev

2

你可以对它进行排序，例如 finalArray.sort()。 - Satpal

我不认为你有其他的选择，除了事后对它们进行排序。如果你仔细想一想，在你的情况下，“保持顺序”会导致冲突，你想要保留第一个数组的顺序还是第二个数组的顺序（如果它们有不同的顺序）？第三个呢？哪些标准必须适用？ - Kaddath

数据不可“排序”。在这个例子中有一个基本数组['A', 'B', 'C', 'D']，但它也可以是['X', '1', 'D', 'EE']（任何其他东西），结果应该保持基本数组的顺序，但在现有项之间添加项目（例如A-bis被添加在A和B之间，不是因为它按字母顺序排序，而是因为它出现在以下数组之一的这两个项之间）。 - MHogge

2

那么我认为你应该编辑你的帖子，使其不像字母顺序排列，并明确必须应用的顺序取决于数组的顺序（先应用第一个数组的顺序，然后是第二个等等），如果是这种情况。你必须意识到，以下数组排序可能会与已经应用的排序冲突，并明确如果发生这种情况，它是否应该被忽略或覆盖现有的排序。 - Kaddath

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TuringCreep · Answer 1

使用二叉搜索树来实现。将所有元素添加到二叉搜索树中，然后按照中序遍历进行遍历。

function BST(){
  this.key = null;
  this.value = null;
  this.left = null;
  this.right = null;

  this.add = function(key}{
   const val = key;

   key = someOrderFunction(key.replace(/\s/,''));
   if(this.key == null) {
      this.key = key;
      this.val = val;

   } else if(key < this.key) {
      if(this.left){
        this.left.add(val);
      } else {
        this.left = new BST();
        this.left.key = key;
        this.left.val = val;
      }
   } else if(key > this.key) {

      if(this.right){
        this.right.add(val);
      } else {
        this.right= new BST();
        this.right.key = key;
        this.right.val = val;
      }
   }

   this.inOrder = function(){
      const leftNodeOrder = this.left ? this.left.inOrder() : [],
            rightNodeOrder = this.right? this.right.inOrder() : [];
      return leftNodeOrder.concat(this.val).concat(this.rightNodeOrder);

   }

}

// MergeArrays uses a BST to insert all elements of all arrays
// and then fetches them sorted in order
function mergeArrays(arrays) {
    const bst = new BST();
    arrays.forEach(array => array.forEach( e => bst.add(e)));
    return bst.inOrder();
}