In Place rotation C++ Practice

Question

我有一个正在运行的旋转函数用于我的"items"int数组.下面的代码完成了它,除了我不必要地转移值.我试图实现"就地"轮换.我的意思是ptrs会增加或减少而不是从数组中获取值.我需要以这种方式"提升"这种方法的效率水平.任何建议？

void quack::rotate(int nRotations)
{
 if ( count <= 1 ) return;
 else  // make sure our ptrs are where we want them.
 {
  intFrontPtr = &items[0].myInt;
  intBackPtr  = &items[count-1].myInt;
 }
 for (int temp = 0; nRotations != 0;)
 {
  if ( nRotations > 0 )
  {
     temp = *intFrontPtr;
    *intFrontPtr = *intBackPtr;
    *intBackPtr  = temp; // Connect temps for the rotation
   --intBackPtr; // Move left [...<-] into the array
  }
  else if ( nRotations < 0 ) 
  {
   temp = *intBackPtr;
   *intBackPtr  = *intFrontPtr;
   *intFrontPtr = temp; // Connect temps for the rotation
   ++intFrontPtr; // Move right [->...] into the array
  }
  if ( intBackPtr  == &items[0].myInt  || 
    intFrontPtr == &items[count-1].myInt ) 
  {
   intFrontPtr = &items[0].myInt; 
   intBackPtr  = &items[count-1].myInt; // need to re-set
   if ( nRotations > 0 ) nRotations--;  // Which ways did we rotate?
   else nRotations++;
  }
 }
 }

哦,是的,我正在尝试练习c ++,并且知道他们有许多功能,这些功能已被编程为已经编程完成...我试图"建立我自己的".我想我已经在语法上得到了它,但效率始终是我奋斗的地方.作为一个新手,我非常感谢对这方面的批评..

Answer 1

在数组中旋转元素有一个老技巧(我在Programming Pearls中首次看到它)

假设您要通过三个元素向左旋转数组.

首先反转前三个元素,然后反转剩余的元素,然后反转整个数组.

Starting Array:
1 2 3 4 5 6 7

After reversing the first three elements
3 2 1 4 5 6 7

After reversing the remaining elements
3 2 1 7 6 5 4

Finally reverse the entire array to get the final rotated array
4 5 6 7 1 2 3

可以在适当的位置反转阵列的部分,因此您不需要任何额外的内存.

Answer 2

您可以保留数据,并有一个"基本索引"成员来指示数组应该从哪里开始.然后,您需要在访问阵列时使用它来调整索引.阵列本身应该是私有的,并且只能通过进行调整的访问器函数来访问.像这样的东西:

class quack
{
public:
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {}
    ~quack() {delete [] items;}

    void rotate(int n)      {base = (base + n) % size;}
    Item &operator[](int i) {return items[(base + i) % size];}

private:
    quack(quack const&) = delete;          // or implement these if you want
    void operator=(quack const&) = delete; // the container to be copyable

    Item *items;
    int   size;
    int   base;
};

虽然我称之为RotatableArray,而不是quack.

Answer 3

一项一项地轮换确实不是办法。如果你做的事情超过 2 或 3 圈，它就会变得非常慢非常快。

编辑：作为最后的想法...将元素放入（双）链接的“循环”列表中（因此最终元素指向第一个元素），将需要旋转以仅将头指针移动几个元素。（头指针是指示循环列表中哪个元素是开始的指针）。

这是迄今为止对元素列表进行旋转的最快（也是最简单）的方法