找出旧数组变成新数组的操作

2020-05-16

面试时候的一道算法题。
给出新旧两个数组，找出旧数组演变成新数组的一个可行的operations。operations可能包含的操作有remove/insert/swap三种。

思路：先通过remove/insert使得旧数组和新数组有一样的元素，然后再通过swap演变成和新数组一样。

给出brute force的解法：

const findOperations = function(oldArr, newArr) {
    const makeMap = arr=>arr.reduce((prev, v, i)=>{
        prev.set(v, (prev.get(v) || 0) + 1);
        return prev;
    }, new Map());
    const oldMap = makeMap(oldArr);
    const newMap = makeMap(newArr);

    const inserts = new Map();
    const removes = new Map();
    const swap = new Map();

    const findInsert = function() {
        for(let [v, count] of newMap) {
            if(!oldMap.get(v)) {
                inserts.set(v, count)
            }else if(oldMap.get(v)<count) {
                inserts.set(v, count - oldMap.get(v));
            }
        }
    }

    const findRemove = function() {
        for(let [v, count] of oldMap) {
            if(!newMap.get(v)) {
                removes.set(v, count)
            }else if(oldMap.get(v)>newMap.get(v)) {
                removes.set(v, count - newMap.get(v));
            }
        }
    }

    findInsert();
    findRemove();

    const operations = [];
    const removeOld = function(v, count) {
        for(let i = 0; i<count; i++) {
            const index = oldArr.indexOf(v);//这里无需再判断-1了
            operations.push(["remove", index]);
            oldArr = oldArr.slice(0, index).concat(oldArr.slice(index+1));
        }
    };

    const insertOld = function(v, count) {
        for(let i = 0; i<count; i++) {
            operations.push(["insert", oldArr.length, v]);
            oldArr.push(v);
        }
    };

    for(let [v, count] of removes) {
        removeOld(v, count);
    }

    for(let [v, count] of inserts) {
        insertOld(v, count);
    }

    let i = 0;
    while(i<newArr.length) {
        if(oldArr[i]==newArr[i]) {
            i++;
            continue;
        }
        const swapIndex = oldArr.indexOf(newArr[i], i+1);
        const tmp = oldArr[i];
        oldArr[i] = oldArr[swapIndex];
        oldArr[swapIndex] = tmp;
        swap.set(i, swapIndex);
        i++;
    }
    
    for(let [v, swapIndex] of swap) {
        operations.push(["swap", v, swapIndex]);
    }

    return operations;
};


//test code:
const oldArr = [1, 2, 3];
const newArr = [4, 3];
console.log(findOperations(oldArr, newArr));

//output
[ 
  [ 'remove', 0 ],//移除第0个元素
  [ 'remove', 0 ],
  [ 'insert', 1, 4 ],//在索引1的位置插入4
  [ 'swap', 0, 1 ] //交换索引0和索引1的元素
]