我在最近的一次采访中遇到了这个问题：
给定一个表示在该位置插入数字的对的数组，我们需要找到最终的排列方式。如果该位置已经有一个数字，则需要将数组从该位置向右移动，然后将该数字放在所需的位置。
例如A = {0，1，2，3，4}，B = {0,1,2,2}（Ai代表一个数字，Bi代表其期望的位置），因此，数组C可以按以下方式填充：
C = {0，_，_，_，_} => {0,1，_，_，_} => {0,2，_，_} => {0,3,1 ，2，_} => {0,4,2}
内容：0
我们需要找到最终的数组C。我需要比对这种解决方案施加蛮力更好的方法。提前致谢。
首先，让我们考虑一下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,val)
node.tn++
return
if curIdx > i:
insertElemBefore(node,val)
node = node.next
//we could not find any elem to shift
//just insert elem at the end
function insertElem(L,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,2]))