比较两个字符串数组时如何识别主动移动而非受级联影响的元素

核心逻辑 #

• 被动位移的元素会保持原数组的相对顺序，只有主动移动的元素会打破这个顺序
• 我们通过计算数组b映射到原数组a下标序列的最长递增子序列（LIS），得到的就是所有保持原有相对顺序的被动元素集合
• 不在这个最长递增子序列中的元素，就是主动移动的元素

实现代码 #

function findMovedElems(a, b) {
  // 假设入参两个数组元素完全一致且无重复元素
  const aIndexMap = new Map(a.map((val, idx) => [val, idx]));
  // 生成b中元素对应a的下标序列
  const idxSequence = b.map(val => aIndexMap.get(val));
  
  // 计算最长递增子序列对应的b数组下标
  function getLISIndexes(arr) {
    const tails = [];
    const prevIndices = new Array(arr.length).fill(-1);
    const tailIndices = new Array(arr.length).fill(-1);
    
    for (let i = 0; i < arr.length; i++) {
      const num = arr[i];
      let left = 0, right = tails.length;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (tails[mid] < num) left = mid + 1;
        else right = mid;
      }
      if (left === tails.length) {
        tails.push(num);
      } else {
        tails[left] = num;
      }
      tailIndices[left] = i;
      if (left > 0) {
        prevIndices[i] = tailIndices[left - 1];
      }
    }
    
    // 回溯得到完整LIS的下标
    const lisIndexes = [];
    let current = tailIndices[tails.length - 1];
    while (current !== -1) {
      lisIndexes.unshift(current);
      current = prevIndices[current];
    }
    return lisIndexes;
  }
  
  const lisIndexes = getLISIndexes(idxSequence);
  const lisElementSet = new Set(lisIndexes.map(idx => b[idx]));
  // 过滤出不在LIS中的主动移动元素
  return b.filter(val => !lisElementSet.has(val));
}

// 测试示例
const a = [1, 2, 3, 4, 5, 6];
const b = [1, 5, 6, 2, 3, 4];
console.log(findMovedElems(a, b)); // 返回 [5, 6]

规则补充 #

如果出现多个等长的最长递增子序列的场景，可以额外增加判断条件：优先将在b中的索引小于在a中的索引（即被前移）的元素判定为主动移动元素，符合常规操作下的主动移动行为特征。

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