输入两个 list ,输出尽可能少但是完全的描述出两个 list 之间的差异
例 1: ABCD 、ACBD 输出 1 位置顺序不一致、2 位置顺序不一致
例 2: ABCD 、ACD 输出 list2 1 位置缺少 B ( list1 1 位置多 B )
例 3: ABCD 、AFCD 输出 位置 1 字符不同
想问问大佬们有没有现成的算法,或者提供一下思路,个人感觉和 git diff 的时候的行比较类似(每个元素看作一行)。但是网上找到的的讲 Myers 有点难懂,感觉也不是偏向于行比较,而是偏向于同行的字符串比较(我理解可能有偏差)
1
soap520 2022-10-10 21:56:14 +08:00 1
听起来有点像是最小编辑距离。
|
2
Jooooooooo 2022-10-10 22:03:34 +08:00
感觉你这还是定义问题.
ABCD 和 ADBC 是 D 多了还是 BC 是错的? |
3
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 |
4
leonshaw 2022-10-10 22:42:10 +08:00
LCS 基础上处理一下输出
|
5
Anarchy 2022-10-11 00:31:23 +08:00
一般再前端列表展示上会需要比较新列表与旧列表数据的不同,转换为增删改移动,然后做对应的动画效果。你要的就是这种效果吧,算法也是 Myers's difference algorithm 。
|
6
ipwx 2022-10-11 00:33:25 +08:00 1
|
7
chihiro2014 2022-10-11 01:02:28 +08:00
比较 size ,然后 removeall 看看有没有剩余
|
8
ericls 2022-10-11 02:28:55 +08:00 via iPhone
你要的是 intention 还是 diff?
|
9
xuanbg 2022-10-11 09:07:22 +08:00
集合没有顺序,所以 a,b,c,d 和 a,c,b,d 是相同的。要比较集合是否相同,在数学上就是取两个集合的差集,差集为空,则集合相等。
|
10
visper 2022-10-11 09:19:08 +08:00
google:最小编辑距离输出编辑过程
|
11
AoEiuV020CN 2022-10-11 10:42:59 +08:00
第一反应是安卓有个现成的 DiffUtil, 就是算出两个列表数据的差异,然后刷新列表控件用的,
https://android.googlesource.com/platform/frameworks/support/+/refs/heads/androidx-main/recyclerview/recyclerview/src/main/java/androidx/recyclerview/widget/DiffUtil.java |
12
ruanimal 2022-10-11 11:46:20 +08:00
可以看看 python 的 difflib 内置库
|
13
zmal 2022-10-11 17:42:17 +08:00
google 有个开源项目叫 diff-match-patch
|