Нахождение окончательной договоренности

Question

Я сталкивался с этим вопросом в недавнем интервью:

Учитывая массив пар, представляющих число, вставленное в какую позицию, нам нужно найти окончательное расположение. Если в этой позиции уже есть число, нам нужно переместить массив из этой позиции вправо и поместить это число в нужную позицию.

например, A = {0, 1, 2, 3, 4},B = {0, 1, 2, 1, 2} (Ai представляет число, а Bi представляет желаемое положение), поэтому массив C можно заполнить следующим образом:

C = {0, _, _, _, _} => {0,1, _, _, _} => {0,1,2, _, _} => {0,3,1,2, _} => {0,3, 4,1,2}

Содержит: 0 <= Ai, Bi <N (N - длина массива) </p>

Нам нужно найти конечный массив C. Мне нужен лучший подход, чемприменение грубой силы для этого решения. Заранее спасибо.

Answer 1

Сначала давайте рассмотрим оператор T, который для позиции i возвращает T(i) = i+1 (то есть элемент переключен вправо). Очевидно, T(T(i)) = i+2, и мы можем отметить T^n(i) = i+n

Теперь рассмотрим связанный список, чей узел

{
    idx: i,//idx of the value upon insertion (as found in B)
    value:value,
    tn:Number //T^n
}

псевдокод будет похож на

insertElem(L, i, val):
    node = L
    while node
        acc += node.tn //sum all the shifts
        curIdx = node.idx + acc
        if curIdx == i:
            insertElemBefore(node, i, val)
            node.tn++
            return
        if curIdx > i:
            insertElemBefore(node, i, val)
        node = node.next
    //we could not find any elem to shift
    //just insert elem at the end

function insertElem(L, i, val){
    let el = {idx:i, val:val, tn:0}
    let acc = 0;
    let front = L;
    while(L.next){
        let next = L.next;
        acc += next.tn;
        if(acc + next.idx >= i){
            L.next = el;
            if(acc + next.idx == i){
                el.next = next;
                next.tn++;
            }
            return front;
        }
        L = L.next;
    }
    L.next = el;
    el.next = null;
    return front;
}
function main(A,B){
    let L = {next:null}
    B.forEach((idx,i)=>{
        L = insertElem(L, idx, A[i]);
    });
    let v = [];
    while(L = L.next){
        v.push(L.val);
    }
    return v;
}
console.log(main([0,1,2,3,4],[0,1,2,1,2]))