改进从 O(n) 到 O(1) 的双端队列移动

Question

任务是队列中有 N 个号码。并且原始序列是从 1 到 N。 “移动a b”的意思是移动a前面的所有数字（包括a）然后将它们插入 b 的前面（不改变顺序）并在 "Exit" 出现时输出整个队列。

这是我处理 "Move":

的代码

//I establish q & q1 deque

while(cin>>commend){
    if(commend == "Move"){
         cin>>a>>b;
         int checka,checkb = 0;

            //search for a,b position
            //it1,it2 are both iterators

            for(int m = 0; m < num ; m++){
                if(q[m] == a){
                    it1 = q.begin()+m;
                    checka = 1;
                }
                else if(q[m] == b){
                    it2 = q.begin()+m;
                    con2 = m; //store m in con2 to use below
                    checkb = 1;
                }
                else if( checka == 1 && checkb == 1)
                    break;
            }

            //con is also a iterator
            //q1 is a new deque to store the elements before (include)number"a" 
            //procedures below are moving the numbers before(include)"a" and push_front the elements between number "a" and number "b"

            for(con = it1; con>= q.begin() ; con--)
                q1.push_front(*con);
            for(con = it2; con > it1+1; con--){
                q1.push_front(*con);

            }

            //copy the "swaped" elements from q1 to q
            //and clear q1

            for(int m = 0; m<con2-1; m++)
                q[m] = q1[m];
            q1.clear();
    }
}

但是速度是O(N)，如果需要用O(1)完成任务，我不知道在哪里可以改进。

除了构建链表之外还有什么建议吗？

Answer 1

您可以维护队列中号码的链表加上索引（散列，如 std::unordered_map），每个号码作为指向队列中号码的键。要更改顺序，您只需在 O(1) 时间内在索引中查找 a 和 b，转到列表中的数字并交换它们的链接指针以更改它们的顺序，再次在 O(1) 时间内。

Answer 2

您不能在 O(1) 中执行 Move 功能。这是因为复杂性由搜索和创建操作共同决定。您的搜索操作需要 O(n)，并且您不能减少它，除非并且直到您更改数据结构（您不想这样做）。即使你，假设你在O(1)中搜索，如果数据存储在一个连续的内存块中，你将只能在O(1)中进行复制操作，然后你可以使用memcpy()。但是，您的搜索操作永远不会在 O(n) 下进行，因此根据我的说法，没有改变渐近边界的余地。此外，如果 a 和 b 相等，您的程序将不会执行任何操作。

改进从 O(n) 到 O(1) 的双端队列移动

Improvement deque movement from O(n) to O(1)

c++

algorithm

performance

deque