一个队列, 每次出队一个放到队尾, 再出队一个输出, 直到队列为空, 知道最后的输出顺序, 求原始队列的顺序.
思路
- 可以理解为把原始队列里的每一个元素当成一个
pair<index, num>
- 对
numBefore
和 indexBefore
相应的相同的操作同时, 其对应关系保持不变
- 现在已知
numAfter
的排列, indexBefore
的排列
- 对
indexBefore
进行相同的操作, 得到 indexAfter
, 从而得到了 pair<index, num>
, 即 numBefore
中 index
与 num
的对应关系, 这就可以还原 numBefore
了
查看看代码
class Solution {
public int[] rawSeq(int[] nums) {
Queue<Integer> q = new LinkedList<>();
int []raw = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
q.offer(i);
}
int index = 0;
while (!q.isEmpty()) {
raw[q.poll()] = nums[index++];
if (!q.isEmpty()){
q.offer(q.poll());
}
}
return raw;
}
}