如何对比两个 list 的差异

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 767 天前的主题，其中的信息可能已经有所发展或是发生改变。

输入两个 list ，输出尽可能少但是完全的描述出两个 list 之间的差异

例 1: ABCD 、ACBD 输出 1 位置顺序不一致、2 位置顺序不一致

例 2： ABCD 、ACD 输出 list2 1 位置缺少 B （ list1 1 位置多 B ）

例 3： ABCD 、AFCD 输出位置 1 字符不同

想问问大佬们有没有现成的算法，或者提供一下思路，个人感觉和 git diff 的时候的行比较类似（每个元素看作一行）。但是网上找到的的讲 Myers 有点难懂，感觉也不是偏向于行比较，而是偏向于同行的字符串比较（我理解可能有偏差）

abcd

list

字符

输出

13 条回复 • 2022-10-11 17:42:17 +08:00

soap520

2022-10-10 21:56:14 +08:00

听起来有点像是最小编辑距离。

Jooooooooo

2022-10-10 22:03:34 +08:00

感觉你这还是定义问题.

ABCD 和 ADBC 是 D 多了还是 BC 是错的?

DiamondYuan

2022-10-10 22:16:00 +08:00

```

/**
* diff 函数
* @param {any} newList 新数组
* @param {any} oldList 旧数组
*/
const diff = function(newList, oldList) {
// lastIndex：即访问过元素的最右下标
let lastIndex = 0;

// 遍历新数组
for(let i = 0, len = newList.length; i < len; i++) {
// 查找当前元素在旧数组的下标
let index = getIndex(newList[i], oldList);

// 若该元素在旧数组中存在
if(index !== -1) {
// 若该元素在旧数组的下标小于最右下标 lastIndex
if(index < lastIndex) {
// 移动元素：from index to i
move(newList[i], i, index);
}

// 更新 lastIndex ，取 index 和 lastIndex 的较大者
lastIndex = Math.max(index, lastIndex);
}
// 若该元素不在旧数组，说明这是个新加入元素
else {
// 插入元素：append to i
append(newList[i], i);
}
}

// 遍历旧数组
for(let i = 0, len = oldList.length; i < len; i++) {
// 若发现当前元素在新数组中不存在，说明这个元素需要移除
if(getIndex(oldList[i], newList) === -1) {
// 移除元素：remove from i
remove(oldList[i], i);
}
}
}

/**
* 找出元素在数组的下标，找不到返回-1
* @param {T} item 要找的元素
* @param {Array<T>} list 目标数组
*/
const getIndex = function(item, list) {
// 对比 key
return list.findIndex(i => i.key === item.key);
}

```

你这个听起来很像前端的 diff

https://github.com/phenomLi/Blog/issues/24