合并数组并保持排序
Merge arrays and keep ordering
注意
根据@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 之间，因此位于 X 和 [=18= 之间] 在最终输出中。
我知道可能会出现冲突，但这里有以下规则：
- 每个项目都应出现在最终输出中。
- 如果一个项目出现在不同位置的多个数组中，第一个出现的是正确的（跳过其他）。
到目前为止，我所做的是使用
将所有这些数组合并为一个数组
const merged = [].concat.apply([], arrays);
（比照）。
然后使用 中的代码片段获取唯一值：
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"
]
欢迎任何帮助！
谢谢。
您可以将 .concat() 与 Set 结合使用以获得唯一值的结果数组：
const data = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
const result = [...new Set([].concat(...data))].sort((a, b) => a.localeCompare(b));
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
展平、删除重复项和排序可以更简单：
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D'],
];
console.log(
arrays
.flat()
.filter((u, i, all) => all.indexOf(u) === i)
.sort((a, b) => a.localeCompare(b)),
);
或根据 Mohammad Usman 的事件更简单，现已删除 post:
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D'],
];
console.log(
[...new Set([].concat(...arrays))].sort((a, b) =>
a.localeCompare(b),
),
);
为此使用 BST。将所有元素加入到bst中，然后依次遍历
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();
}
使用 array#concat 创建单个数组，然后使用 Set 从该数组中获取唯一值，然后对数组进行排序。
const arrays = [ ['A', 'B', 'C', 'D'], ['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'], ['A', 'A-bis', 'B', 'C', 'D'], ['A', 'C', 'E'], ['A', 'B', 'C', 'D'] ],
result = [...new Set([].concat(...arrays))].sort();
console.log(result);
我只是将数组展平，将它们映射为对象的键（从而删除双精度数），然后对最终结果进行排序
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
const final = Object.keys( arrays.flat().reduce( (aggregate, entry) => {
aggregate[entry] = '';
return aggregate;
}, {} ) ).sort( (x1, x2) => x1.localeCompare(x2) );
console.log( final );
- 合并
[].concat.apply([], arrays)
- 查找uniq
[...new Set(merged)]
- 排序
.sort()
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
let merged = [].concat.apply([], arrays); // merge array
let sort = [...new Set(merged)].sort(); // find uniq then sort
console.log(sort);
对于您的代码，合并后您需要删除重复项。所以你会得到唯一的数组。
使用array.sort对数组进行排序。
希望这能解决问题。
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
]
const merged = [].concat.apply([], arrays);
const unique = Array.from(new Set(merged))
const sorted = unique.sort()
console.log("sorted Array", sorted)
// Single Line
const result = [...new Set([].concat(...arrays))].sort();
console.log("sorted Array single line", result)
解决有趣的问题；我想我只成功了一部分。
- 我忽略了
B -> A -> T 与 T -> B -> A 的 "underspecified" 示例
- 效率很低
仍在发帖，因为我认为它可能会帮助您解决问题。这是我的方法：
第 1 步：创建简单索引
我们正在创建一个对象，对于嵌套数组中的每个唯一元素，跟踪它已经成功或之前的元素：
{
"X": { prev: Set({}), next: Set({ "D", "H", "B", "K", "Z", "A", "M", "T" })
"M": { prev: Set({ "X" }), next: Set({ "D", "H", "B" })
// etc.
}
我把它命名为"naive"是因为这些Set只包含一层深度的信息。
I.e.: they only report relations between elements that were in the same array. They cannot see the M comes before the K because they were never in the same array.
第 2 步：递归加入索引
这是我忽略了人们可能有的所有大 O 问题的地方。我以递归方式合并索引：M 的 next 是 D, H, B 的 next 的连接。递归直到找到没有 next 的元素，即 T 或 A.
第 3 步：创建一个遵循排序索引的排序器：
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0 ;
此函数创建一个排序方法，该方法使用生成的索引查找任意两个元素之间的排序顺序。
综合考虑：
(function() {
const naiveSortIndex = xss => xss
.map(xs =>
// [ prev, cur, next ]
xs.map((x, i, xs) => [
xs.slice(0, i), x, xs.slice(i + 1)
])
)
// flatten
.reduce((xs, ys) => xs.concat(ys), [])
// add to index
.reduce(
(idx, [prev, cur, next]) => {
if (!idx[cur])
idx[cur] = {
prev: new Set(),
next: new Set()
};
prev.forEach(p => {
idx[cur].prev.add(p);
});
next.forEach(n => {
idx[cur].next.add(n);
});
return idx;
}, {}
);
const expensiveSortIndex = xss => {
const naive = naiveSortIndex(xss);
return Object
.keys(naive)
.reduce(
(idx, k) => Object.assign(idx, {
[k]: {
prev: mergeDir("prev", naive, k),
next: mergeDir("next", naive, k)
}
}), {}
)
}
const mergeDir = (dir, idx, k, s = new Set()) =>
idx[k][dir].size === 0
? s
: Array.from(idx[k][dir])
.reduce(
(s, k2) => mergeDir(dir, idx, k2, s),
new Set([...s, ...idx[k][dir]])
);
// Generate a recursive sort method based on an index of { key: { prev, next } }
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0;
const uniques = xs => Array.from(new Set(xs));
// App:
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 sortIndex = expensiveSortIndex(arrays);
const sorter = indexSorter(sortIndex);
console.log(JSON.stringify(
uniques(arrays.flat()).sort(sorter)
))
}())
建议
我想这个问题的优雅解决方案可能能够通过使用链表/树状结构并通过遍历直到元素在正确的索引处注入元素来跳过 Set 的所有合并找到了 prev/next。
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(','));
每个数组实际上都是一组规则，告诉元素之间的相对顺序是什么。最终列表应 return 所有元素，同时尊重所有规则定义的相对顺序。
有些解决方案已经解决了最初的请求，有些甚至没有解决那个问题（所有建议使用 sort 的方法都没有抓住问题的重点）。尽管如此，none 提出了一个通用的解决方案。
问题
如果我们看一下 OP 中提出的问题，规则就是这样定义元素之间的相对位置的：
M K -> Z T
^ \ ^ \ ^
/ v/ v/
X -> D ------> H -> B -> A
因此，很容易看出我们的数组以X开头。下一个元素可以是D和M。但是，D要求M已经在数组中。这就是为什么我们将 M 作为我们的下一个元素，然后是 D。接下来，D 指向 K 和 H。但是由于 H 有一些其他的前任，直到现在才收集到，并且 K 有 none （实际上它有D，但它已经收集在列表中），我们将放K和Z，然后放H。
H同时指向T和B，其实先放哪个并不重要。所以，最后三个元素可以是以下三个顺序中的任何一个：
- T、B、A
- B、A、T
- B、T、A
我们还要考虑稍微复杂一点的情况。规则如下：
['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 上）。
解决方案
我的想法是从每个元素创建一个节点。然后使用该节点来跟踪所有直接后继者和直接前驱者。之后我们会找到所有没有前辈的元素，并从那里开始“收集”结果。如果我们来到有多个前驱的节点，但其中一些没有被收集，我们将在那里停止递归。可能会发生一些后继者已经在其他路径中收集的情况。我们会跳过那个继任者。
function mergeAndMaintainRelativeOrder(arrays/*: string[][]*/)/*: string[]*/ {
/*
interface NodeElement {
value: string;
predecessor: Set<NodeElement>;
successor: Set<NodeElement>;
collected: boolean;
}
*/
const elements/*: { [key: string]: NodeElement }*/ = {};
// For every element in all rules create NodeElement that will
// be used to keep track of immediate predecessors and successors
arrays.flat().forEach(
(value) =>
(elements[value] = {
value,
predecessor: new Set/*<NodeElement>*/(),
successor: new Set/*<NodeElement>*/(),
// Used when we form final array of results to indicate
// that this node has already be collected in final array
collected: false,
}),
);
arrays.forEach((list) => {
for (let i = 0; i < list.length - 1; i += 1) {
const node = elements[list[i]];
const nextNode = elements[list[i + 1]];
node.successor.add(nextNode);
nextNode.predecessor.add(node);
}
});
function addElementsInArray(head/*: NodeElement*/, array/*: string[]*/) {
let areAllPredecessorsCollected = true;
head.predecessor.forEach((element) => {
if (!element.collected) {
areAllPredecessorsCollected = false;
}
});
if (!areAllPredecessorsCollected) {
return;
}
array.push(head.value);
head.collected = true;
head.successor.forEach((element) => {
if (!element.collected) {
addElementsInArray(element, array);
}
});
}
const results/*: string[]*/ = [];
Object.values(elements)
.filter((element) => element.predecessor.size === 0)
.forEach((head) => {
addElementsInArray(head, results);
});
return results;
}
console.log(mergeAndMaintainRelativeOrder([
['X', 'D', 'H', 'B'],
['X', 'D', 'K', 'Z', 'H', 'B', 'A'],
['X', 'M', 'D', 'H', 'B'],
['X', 'H', 'T'],
['X', 'D', 'H', 'B'],
]));
console.log(mergeAndMaintainRelativeOrder([
['10', '11', '12', '1', '2'],
['11', '12', '13', '2'],
['9', '13'],
['9', '10'],
]));
大O
如果我们说n是规则的数量，m是每个规则中元素的数量，那么这个算法的复杂度是O(n*m )。这考虑到了 Set implementation for the JS is near O(1).
我的解决方案不注重效率，所以我不会在大型阵列上尝试这个。但它对我来说很好。
想法是多次遍历所有元素，并且只在以下三种情况之一中将元素插入排序数组：
- 当前元素在其数组中排在首位，其后继元素之一在排序数组中排在首位。
- 当前元素在其数组中排在最后，其前身之一在排序数组中排在最后。
- 前面的元素在排序数组中，并且当前元素的后继元素之一直接接在排序数组中的前面元素之后。
对于当前的问题，如上所述，T和B, A之间的顺序不是唯一确定的。为了处理这个问题，我使用了一个标志 force，当在迭代期间无法进行新插入时，它采用任何合法选项。
问题中的以下规则未在我的解决方案中实现。 如果一个项目出现在多个数组的不同位置，第一个出现的是正确的（跳过其他）。数组之间没有层次结构。然而，应该很容易实施所需的检查，如果不满意，continue。
let merge = (arrays) => {
let sorted = [...arrays[0]];
const unused_rules = arrays.slice(1);
let not_inserted = unused_rules.flat().filter((v) => !sorted.includes(v));
let last_length = -1;
let force = false;
// avoids lint warning
const sortedIndex = (sorted) => (v) => sorted.indexOf(v);
// loop until all elements are inserted, or until not even force works
while (not_inserted.length !== 0 && !force) {
force = not_inserted.length === last_length; //if last iteration didn't add elements, our arrays lack complete information and we must add something using what little we know
last_length = not_inserted.length;
for (let j = 0; j < unused_rules.length; j += 1) {
const array = unused_rules[j];
for (let i = 0; i < array.length; i += 1) {
// check if element is already inserted
if (sorted.indexOf(array[i]) === -1) {
if (i === 0) {
// if element is first in its array, check if it can be prepended to sorted array
const index = array.indexOf(sorted[0]);
if (index !== -1 || force) {
const insert = array.slice(0, force ? 1 : index);
sorted = [...insert, ...sorted];
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
} else if (i === array.length - 1) {
// if element is last in its array, check if it can be appended to sorted array
const index = array.indexOf(sorted[sorted.length - 1]);
if (index !== -1 || force) {
const insert = array.slice(force ? array.length - 1 : index + 1);
sorted = [...sorted, ...insert];
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
} else {
const indices = array.map(sortedIndex(sorted)); // map all elements to its index in sorted
const predecessorIndexSorted = indices[i - 1]; // index in the sorted array of the element preceding current element
let successorIndexArray;
if (force) {
successorIndexArray = i + 1;
} else {
successorIndexArray = indices.indexOf(predecessorIndexSorted + 1); // index in the current array of the element succeeding the current elements predecessor in the sorted array
}
if (predecessorIndexSorted !== -1 && successorIndexArray !== -1) {
// insert all elements between predecessor and successor
const insert = array.slice(i, successorIndexArray);
sorted.splice(i, 0, ...insert);
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
}
}
}
}
}
return sorted;
};
事实上，规则如果一个项目出现在多个数组的不同位置，第一个出现的是正确的（跳过其他）。有点模糊。例如使用下面的数组，以 arrays[3] 作为排序数组结束是否可以，因为它不违反任何元素的首次出现，或者应该 arrays[2] 优先？
const arrays = [['a', 'b', 'd'],
['a', 'c', 'd'],
['a', 'b', 'c', 'd']
['a', 'c', 'b', 'd']]
注意
根据@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 之间，因此位于 X 和 [=18= 之间] 在最终输出中。
我知道可能会出现冲突，但这里有以下规则：
- 每个项目都应出现在最终输出中。
- 如果一个项目出现在不同位置的多个数组中，第一个出现的是正确的（跳过其他）。
到目前为止，我所做的是使用
将所有这些数组合并为一个数组const merged = [].concat.apply([], arrays);
（比照）。
然后使用 中的代码片段获取唯一值：
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"
]
欢迎任何帮助！
谢谢。
您可以将 .concat() 与 Set 结合使用以获得唯一值的结果数组：
const data = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
const result = [...new Set([].concat(...data))].sort((a, b) => a.localeCompare(b));
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
展平、删除重复项和排序可以更简单：
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D'],
];
console.log(
arrays
.flat()
.filter((u, i, all) => all.indexOf(u) === i)
.sort((a, b) => a.localeCompare(b)),
);
或根据 Mohammad Usman 的事件更简单，现已删除 post:
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D'],
];
console.log(
[...new Set([].concat(...arrays))].sort((a, b) =>
a.localeCompare(b),
),
);
为此使用 BST。将所有元素加入到bst中，然后依次遍历
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();
}
使用 array#concat 创建单个数组，然后使用 Set 从该数组中获取唯一值，然后对数组进行排序。
const arrays = [ ['A', 'B', 'C', 'D'], ['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'], ['A', 'A-bis', 'B', 'C', 'D'], ['A', 'C', 'E'], ['A', 'B', 'C', 'D'] ],
result = [...new Set([].concat(...arrays))].sort();
console.log(result);
我只是将数组展平，将它们映射为对象的键（从而删除双精度数），然后对最终结果进行排序
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
const final = Object.keys( arrays.flat().reduce( (aggregate, entry) => {
aggregate[entry] = '';
return aggregate;
}, {} ) ).sort( (x1, x2) => x1.localeCompare(x2) );
console.log( final );
- 合并
[].concat.apply([], arrays) - 查找uniq
[...new Set(merged)] - 排序
.sort()
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
];
let merged = [].concat.apply([], arrays); // merge array
let sort = [...new Set(merged)].sort(); // find uniq then sort
console.log(sort);
对于您的代码，合并后您需要删除重复项。所以你会得到唯一的数组。
使用array.sort对数组进行排序。
希望这能解决问题。
const arrays = [
['A', 'B', 'C', 'D'],
['A', 'B', 'B-bis', 'B-ter', 'C', 'D', 'D-bis'],
['A', 'A-bis', 'B', 'C', 'D'],
['A', 'C', 'E'],
['A', 'B', 'C', 'D']
]
const merged = [].concat.apply([], arrays);
const unique = Array.from(new Set(merged))
const sorted = unique.sort()
console.log("sorted Array", sorted)
// Single Line
const result = [...new Set([].concat(...arrays))].sort();
console.log("sorted Array single line", result)
解决有趣的问题；我想我只成功了一部分。
- 我忽略了
B -> A -> T与T -> B -> A 的 "underspecified" 示例
- 效率很低
仍在发帖，因为我认为它可能会帮助您解决问题。这是我的方法：
第 1 步：创建简单索引
我们正在创建一个对象，对于嵌套数组中的每个唯一元素，跟踪它已经成功或之前的元素：
{
"X": { prev: Set({}), next: Set({ "D", "H", "B", "K", "Z", "A", "M", "T" })
"M": { prev: Set({ "X" }), next: Set({ "D", "H", "B" })
// etc.
}
我把它命名为"naive"是因为这些Set只包含一层深度的信息。
I.e.: they only report relations between elements that were in the same array. They cannot see the
Mcomes before theKbecause they were never in the same array.
第 2 步：递归加入索引
这是我忽略了人们可能有的所有大 O 问题的地方。我以递归方式合并索引：M 的 next 是 D, H, B 的 next 的连接。递归直到找到没有 next 的元素，即 T 或 A.
第 3 步：创建一个遵循排序索引的排序器：
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0 ;
此函数创建一个排序方法，该方法使用生成的索引查找任意两个元素之间的排序顺序。
综合考虑：
(function() {
const naiveSortIndex = xss => xss
.map(xs =>
// [ prev, cur, next ]
xs.map((x, i, xs) => [
xs.slice(0, i), x, xs.slice(i + 1)
])
)
// flatten
.reduce((xs, ys) => xs.concat(ys), [])
// add to index
.reduce(
(idx, [prev, cur, next]) => {
if (!idx[cur])
idx[cur] = {
prev: new Set(),
next: new Set()
};
prev.forEach(p => {
idx[cur].prev.add(p);
});
next.forEach(n => {
idx[cur].next.add(n);
});
return idx;
}, {}
);
const expensiveSortIndex = xss => {
const naive = naiveSortIndex(xss);
return Object
.keys(naive)
.reduce(
(idx, k) => Object.assign(idx, {
[k]: {
prev: mergeDir("prev", naive, k),
next: mergeDir("next", naive, k)
}
}), {}
)
}
const mergeDir = (dir, idx, k, s = new Set()) =>
idx[k][dir].size === 0
? s
: Array.from(idx[k][dir])
.reduce(
(s, k2) => mergeDir(dir, idx, k2, s),
new Set([...s, ...idx[k][dir]])
);
// Generate a recursive sort method based on an index of { key: { prev, next } }
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0;
const uniques = xs => Array.from(new Set(xs));
// App:
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 sortIndex = expensiveSortIndex(arrays);
const sorter = indexSorter(sortIndex);
console.log(JSON.stringify(
uniques(arrays.flat()).sort(sorter)
))
}())
建议
我想这个问题的优雅解决方案可能能够通过使用链表/树状结构并通过遍历直到元素在正确的索引处注入元素来跳过 Set 的所有合并找到了 prev/next。
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(','));
每个数组实际上都是一组规则，告诉元素之间的相对顺序是什么。最终列表应 return 所有元素，同时尊重所有规则定义的相对顺序。
有些解决方案已经解决了最初的请求，有些甚至没有解决那个问题（所有建议使用 sort 的方法都没有抓住问题的重点）。尽管如此，none 提出了一个通用的解决方案。
问题
如果我们看一下 OP 中提出的问题，规则就是这样定义元素之间的相对位置的：
M K -> Z T
^ \ ^ \ ^
/ v/ v/
X -> D ------> H -> B -> A
因此，很容易看出我们的数组以X开头。下一个元素可以是D和M。但是，D要求M已经在数组中。这就是为什么我们将 M 作为我们的下一个元素，然后是 D。接下来，D 指向 K 和 H。但是由于 H 有一些其他的前任，直到现在才收集到，并且 K 有 none （实际上它有D，但它已经收集在列表中），我们将放K和Z，然后放H。
H同时指向T和B，其实先放哪个并不重要。所以，最后三个元素可以是以下三个顺序中的任何一个：
- T、B、A
- B、A、T
- B、T、A
我们还要考虑稍微复杂一点的情况。规则如下：
['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 上）。
解决方案
我的想法是从每个元素创建一个节点。然后使用该节点来跟踪所有直接后继者和直接前驱者。之后我们会找到所有没有前辈的元素，并从那里开始“收集”结果。如果我们来到有多个前驱的节点，但其中一些没有被收集，我们将在那里停止递归。可能会发生一些后继者已经在其他路径中收集的情况。我们会跳过那个继任者。
function mergeAndMaintainRelativeOrder(arrays/*: string[][]*/)/*: string[]*/ {
/*
interface NodeElement {
value: string;
predecessor: Set<NodeElement>;
successor: Set<NodeElement>;
collected: boolean;
}
*/
const elements/*: { [key: string]: NodeElement }*/ = {};
// For every element in all rules create NodeElement that will
// be used to keep track of immediate predecessors and successors
arrays.flat().forEach(
(value) =>
(elements[value] = {
value,
predecessor: new Set/*<NodeElement>*/(),
successor: new Set/*<NodeElement>*/(),
// Used when we form final array of results to indicate
// that this node has already be collected in final array
collected: false,
}),
);
arrays.forEach((list) => {
for (let i = 0; i < list.length - 1; i += 1) {
const node = elements[list[i]];
const nextNode = elements[list[i + 1]];
node.successor.add(nextNode);
nextNode.predecessor.add(node);
}
});
function addElementsInArray(head/*: NodeElement*/, array/*: string[]*/) {
let areAllPredecessorsCollected = true;
head.predecessor.forEach((element) => {
if (!element.collected) {
areAllPredecessorsCollected = false;
}
});
if (!areAllPredecessorsCollected) {
return;
}
array.push(head.value);
head.collected = true;
head.successor.forEach((element) => {
if (!element.collected) {
addElementsInArray(element, array);
}
});
}
const results/*: string[]*/ = [];
Object.values(elements)
.filter((element) => element.predecessor.size === 0)
.forEach((head) => {
addElementsInArray(head, results);
});
return results;
}
console.log(mergeAndMaintainRelativeOrder([
['X', 'D', 'H', 'B'],
['X', 'D', 'K', 'Z', 'H', 'B', 'A'],
['X', 'M', 'D', 'H', 'B'],
['X', 'H', 'T'],
['X', 'D', 'H', 'B'],
]));
console.log(mergeAndMaintainRelativeOrder([
['10', '11', '12', '1', '2'],
['11', '12', '13', '2'],
['9', '13'],
['9', '10'],
]));
大O
如果我们说n是规则的数量，m是每个规则中元素的数量，那么这个算法的复杂度是O(n*m )。这考虑到了 Set implementation for the JS is near O(1).
我的解决方案不注重效率，所以我不会在大型阵列上尝试这个。但它对我来说很好。
想法是多次遍历所有元素，并且只在以下三种情况之一中将元素插入排序数组：
- 当前元素在其数组中排在首位，其后继元素之一在排序数组中排在首位。
- 当前元素在其数组中排在最后，其前身之一在排序数组中排在最后。
- 前面的元素在排序数组中，并且当前元素的后继元素之一直接接在排序数组中的前面元素之后。
对于当前的问题，如上所述，T和B, A之间的顺序不是唯一确定的。为了处理这个问题，我使用了一个标志 force，当在迭代期间无法进行新插入时，它采用任何合法选项。
问题中的以下规则未在我的解决方案中实现。 如果一个项目出现在多个数组的不同位置，第一个出现的是正确的（跳过其他）。数组之间没有层次结构。然而，应该很容易实施所需的检查，如果不满意，continue。
let merge = (arrays) => {
let sorted = [...arrays[0]];
const unused_rules = arrays.slice(1);
let not_inserted = unused_rules.flat().filter((v) => !sorted.includes(v));
let last_length = -1;
let force = false;
// avoids lint warning
const sortedIndex = (sorted) => (v) => sorted.indexOf(v);
// loop until all elements are inserted, or until not even force works
while (not_inserted.length !== 0 && !force) {
force = not_inserted.length === last_length; //if last iteration didn't add elements, our arrays lack complete information and we must add something using what little we know
last_length = not_inserted.length;
for (let j = 0; j < unused_rules.length; j += 1) {
const array = unused_rules[j];
for (let i = 0; i < array.length; i += 1) {
// check if element is already inserted
if (sorted.indexOf(array[i]) === -1) {
if (i === 0) {
// if element is first in its array, check if it can be prepended to sorted array
const index = array.indexOf(sorted[0]);
if (index !== -1 || force) {
const insert = array.slice(0, force ? 1 : index);
sorted = [...insert, ...sorted];
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
} else if (i === array.length - 1) {
// if element is last in its array, check if it can be appended to sorted array
const index = array.indexOf(sorted[sorted.length - 1]);
if (index !== -1 || force) {
const insert = array.slice(force ? array.length - 1 : index + 1);
sorted = [...sorted, ...insert];
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
} else {
const indices = array.map(sortedIndex(sorted)); // map all elements to its index in sorted
const predecessorIndexSorted = indices[i - 1]; // index in the sorted array of the element preceding current element
let successorIndexArray;
if (force) {
successorIndexArray = i + 1;
} else {
successorIndexArray = indices.indexOf(predecessorIndexSorted + 1); // index in the current array of the element succeeding the current elements predecessor in the sorted array
}
if (predecessorIndexSorted !== -1 && successorIndexArray !== -1) {
// insert all elements between predecessor and successor
const insert = array.slice(i, successorIndexArray);
sorted.splice(i, 0, ...insert);
not_inserted = not_inserted.filter((v) => !insert.includes(v));
force = false;
}
}
}
}
}
}
return sorted;
};
事实上，规则如果一个项目出现在多个数组的不同位置，第一个出现的是正确的（跳过其他）。有点模糊。例如使用下面的数组，以 arrays[3] 作为排序数组结束是否可以，因为它不违反任何元素的首次出现，或者应该 arrays[2] 优先？
const arrays = [['a', 'b', 'd'],
['a', 'c', 'd'],
['a', 'b', 'c', 'd']
['a', 'c', 'b', 'd']]