如何合并两个长度不同的数字deck，保留元素相对顺序且去重

核心思路 #

你的需求本质是求两个数组的去重并集，同时保留原数组的元素相对顺序，有两种合法输出取决于你优先保留哪个数组的排序规则，用哈希集合（Set）实现是效率最高的方案，完全不需要嵌套循环。

实现步骤 #

1. 初始化一个空的哈希集合用于记录已经加入结果的元素，避免重复
2. 优先遍历你想保留顺序的数组，将未在集合中出现的元素加入结果数组，同时将该元素标记到集合中
3. 再遍历另一个数组，同样将未在集合中出现的元素加入结果数组

代码示例 #

如果要得到[1, 15, 2]的结果，优先保留deck2的顺序：

const deck1 = [1, 2]
const deck2 = [1, 15, 2]
const existed = new Set()
const newDeck = []

// 先遍历deck2，优先保留deck2的元素顺序
for (const num of deck2) {
  if (!existed.has(num)) {
    newDeck.push(num)
    existed.add(num)
  }
}
// 再遍历deck1，补充deck2中不存在的元素
for (const num of deck1) {
  if (!existed.has(num)) {
    newDeck.push(num)
    existed.add(num)
  }
}

如果要得到[1, 2, 15]的结果，只要交换两个遍历的顺序，先遍历deck1再遍历deck2即可。

性能说明 #

你担心的哈希表性能问题完全不存在：哈希集合的查询、插入操作均摊时间复杂度都是O(1)，整个方案的总时间复杂度是O(m + n)（m、n分别是两个数组的长度），属于线性复杂度，比嵌套循环的O(m*n)性能高很多，哪怕处理长度上万的数组也不会有性能问题。

原有思路的问题 #

你现在写的双层循环逻辑实际是在求两个数组的交集，无法得到两个数组的全部元素，同时嵌套循环不仅性能差，还会出现重复添加元素的问题，不建议使用。

内容的提问来源于stack exchange，提问作者Arturo