原地旋转 C++实践

Question

我有一个适用于我的“items”int 数组的工作旋转函数。下面的代码完成了它，只是我不必要地传输了值。我试图实现“就地”旋转。我的意思是，ptr 会递增或递减，而不是从数组中获取值。我需要以这种方式“提高”此方法的效率级别。有什么建议吗？

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

有一个旋转数组中元素的老技巧（我第一次在编程珍珠中看到它）

假设您想将数组向左旋转三个元素。

首先反转前三个元素，然后反转其余元素，然后反转整个数组。

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

像往常一样，如果您确实必须物理旋转元素，那么 C++ 的正确答案是使用 std::rotate，它正是您想要做的。

如果您必须手动实现它（作为练习作业），请查看这些 幻灯片。

Answer 4

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

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

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

Answer 5

实际上，做到这一点的方法是使用索引而不是指针。

int to = 0;
int from = (to + nRotations) % count;
if (to == from)
    return;

for (int i=0; i < count; i++) {
   swap(from, to);
   from = advance(from);
   to = advance(to);
}

// ...
static inline int advance(int n, int count) { return (n + 1) % count; }

Answer 6

我可能有另一种解决方案来内联旋转数组。这种方法不像之前提出的那样采用反转元素集的老技巧，而是按如下方式工作：

初始化：（

注意 q = 左移量，n = 数组长度）

1. 确定第一个源元素，该元素位于 x1= q%n
2. 目标元素位于 x2=0 处
3. char, ch1 是 ar[x1] 元素
4. char, ch2 是 ar[x2] 元素

在 i=0 到 n-1 上循环，其中 n = 数组长度

1. 覆盖目标元素 ar[x2] 与 ch1
2. Set ch1 = ch2
3. Set x1 = x2
4. Set x2 = x2 - q
5. 如果 x2 由于上述减法而为负，则向其添加 n
6. ch2 = ar[x2]

以下内容可能有助于解释如何进行这有效。

例如，向左旋转 2 个字符：

abcdefg

cdefgab

x1    ch1    x2    ch2
2     c      0     a
0     a      5     f
5     f      3     d
3     d      1     b
1     b      6     g
6     g      4     e
4     e      2     c

正如您所看到的，这需要不超过 n 次迭代，因此它是线性时间算法，也内联旋转（除了少数临时变量之外不需要额外的存储）。

这是一个实现上述算法的函数，您可以尝试一下：

void rotate(char *ar, int q)
{
    if (strlen(ar) < 2)
    {
        return;
    }

    if (q <= 0)
    {
        return;
    }

    char ch1;
    char ch2;
    int x1;
    int x2;
    int i;
    int n;

    n = strlen(ar);

    q %= n;

    if (q == 0)
    {
        return;
    }

    x1 = q;
    ch1 = ar[x1];
    x2 = 0;
    ch2 = ar[x2];

    for (i=0;i<n;i++)
    {
        ar[x2] = ch1;
        ch1 = ch2;

        x1 = x2;

        x2 -= q;

        if (x2 < 0)
        {
            x2 += n;
        }

        ch2 = ar[x2];
    }
}

Answer 7

这是我通过修改此处的代码得到的：

template<class It>
It rotate(It begin, It const middle, It end)
{
    typename std::iterator_traits<It>::difference_type i = 0, j;
    if (begin != middle && middle != end)
    {
        while ((i = std::distance(begin, middle)) !=
               (j = std::distance(middle,   end)))
        {
            It k = middle;
            std::advance(
                k,
                std::max(typename std::iterator_traits<It>::difference_type(),
                j - i));
            std::swap_ranges(k, end, begin);
            if (i > j) { std::advance(begin, j); }
            else { std::advance(end, -i); }
        }
    }
    return std::swap_ranges(middle - i, middle, middle);
}

Answer 8

这是 sdtom 解决方案的代码

void rotateArray(int arr[], int low, int high)
{
    while  (low<high) {
        int temp = arr[low];
        arr[low]=arr[high];
        arr[high]=temp;
        low++;
        high--;
    }
}
void rotate (int arr[], int k,int uperLimit)
{
    rotateArray(arr,0,k);
    rotateArray(arr,k+1,uperLimit-1);
    rotateArray(arr,0,uperLimit-1);

}

Answer 9

https://stackoverflow.com/q/17119000/2383578：这与此处讨论的内容有些相似。将数组旋转特定量。

Answer 10

有很多方法可以按 d 位进行数组旋转。

1. 块交换算法。
2. 杂耍算法。
3. 反转算法。

下面的链接来自Programming Pearls pdf。看看这个。用代码解释的非常清楚。

http://www.cs.bell-labs.com/cm /cs/pearls/s02b.pdf