javascript - 比较 2 个字符串数组时，确定哪些元素已移动索引

Question

我试图找出比较两个字符串数组时移动了哪些元素。我想找到作为其他值在数组中移动的副作用而显式移动和未移动的元素。请看下面的例子：

const a = [1, 2, 3, 4, 5, 6];
const b = [1, 5, 6, 2, 3, 4];

findMovedElems(a, b) // returns [5, 6] even though [2, 3, 4,] have changed index too - that was caused as a side effect of 5, 6 being moved.

标签： javascriptarraysalgorithm

Answer 1

我没有针对其他情况进行测试（例如数字不在 a 中的 b、重复数字等），但适用于您的示例。

    var a = [1, 2, 3, 4, 5, 6, 7, 8];
    var b = [1, 5, 6, 2, 3, 4, 7, 8];

    function findMovedElems(a, b) {
      let result = [{"status" : 'OK', "arr" : []}]
      // navigate over a and b
      for (let i = 0, j = 0; i < a.length && j < b.length; i++, j++) {
        if (a[i] === b[j]) {
          result[result.length - 1].arr.push(a[i]);
          continue;
        }
        result.push({"status" : 'MOVED', "arr" : [] });
        // search for current b char on a
        for(let i2 = i ; i2 < a.length; i2++) {
          if (a[i2] !== b[j]) {
            continue;
          }
          if (i2 === j) {
              // a and b are synchonized again. Reset i and return to main loop
              result[result.length - 1].status = 'OK';
              j--;// warning: decrementing loop variable
              i = j;// warning: changing loop variable
              break;
          }
          // found move. Read from a and b when is equals
          for (let i3 = i2; i3 < a.length && j < b.length; i3++, j++/* warning: incrementing other loop variable*/) {
              if (a[i3] !== b[j]) {
                break;
              }
              result[result.length - 1].arr.push(a[i3]);
          }//for_i3
          // Go back, because new array possition was readed, and should be read again on main loop
          i--;// warning: decrementing loop variable
          j--;// warning: decrementing loop variable
          if (i === j) {
              result.push({"status" : 'OK', "arr" : [] });
          } else {
              result.push({"status" : 'MOVED_SIDE_EFFECT', "arr" : [] });
          }
          break;
        }//for_i2
      }//for_i
      return result;
    }

    console.log(JSON.stringify(findMovedElems(a, b)));

输出：

[{"status":"OK","arr":[1]},{"status":"MOVED","arr":[5,6]},{"status":"MOVED_SIDE_EFFECT","arr":[2,3,4]},{"status":"OK","arr":[7,8]}]