logo标签列表

C++实践中的原地旋转

c++arraysrotation
5

我已经为我的“items” int数组编写了一个旋转函数。下面的代码可以完成这个任务，但是我不必要地将值传递出去。我试图实现“inplace”旋转。我的意思是指指针会增加或减少，而不是从数组中获取值。通过这种方式，我需要在这种方法中提高效率水平。有什么建议吗？

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++并知道已经有许多已经编程完成的函数可以执行此操作...但我正试图“构建自己的”。我认为我在语法上已经掌握了它，但效率总是让我感到困难。作为一个新手，我非常感谢对这个方面的批评。

10个回答
15

有一种古老的技巧可以旋转数组中的元素（我第一次看到是在《编程珠玑》中）

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

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

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

可以就地反转数组的部分内容，因此您无需额外使用任何内存。

3
那不就是把数组向左旋转吗？ - Nick Meyer
@reinier - 当只触摸每个元素一次时，您如何将数组旋转任意数量的位置？ - sdtom
1
@sdtom：你提到了《编程珠玑》，对吧？同一本书中的“Juggling Algorithm”只会对每个元素进行一次操作（即每个元素只读取一次，只写入一次）。 - AnT stands with Russia
1
@reinier：虽然“juggling算法”可以一次性完成，但在合理的算法中它是效率最低的。对于相当大的输入，最有效的算法是来自《编程珠玑》的“块交换”。而且它也会多次移动元素。 - AnT stands with Russia
非常好，我以前没有见过这个算法。我没有读过《编程珠玑》，所以我认为“Juggling Algorithm”是你追踪每个元素的前任的地方——对吗？它是O(n)的，但是那个算法比你在这里给出的算法具有更糟糕的引用局部性。 - j_random_hacker
显示剩余2条评论
6

您可以保留数据不动，使用“基本索引”成员指示数组应该从哪里开始。然后在访问数组时，需要使用此成员来调整索引。数组本身应该是私有的，并且只能通过执行这个调整的访问器函数来访问。类似以下代码：

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”。
1

逐个旋转并不是正确的方法。如果你需要进行超过2或3次的旋转，它会变得非常缓慢。

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

这绝对是在元素列表上执行旋转的最快（也是最简单）方法。

1
通常情况下，如果您真的需要物理旋转元素，则在C++中正确的答案是使用std::rotate，它可以完全实现您想要做的事情。
如果您必须手动实现（作为练习作业），请参阅John Bentley的“编程珠玑”中的这些 幻灯片 中提供的算法。
0

我可能有一个替代方案来实现数组内联旋转。与之前提出的反转元素集合的老技巧不同，这种方法的工作方式如下：

初始化：

（注意 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. 用 ch1 覆盖目标元素 ar[x2]
  2. 将 ch1 设置为 ch2
  3. 将 x1 设置为 x2
  4. 将 x2 设置为 x2 - q
  5. 如果由于上述减法而导致 x2 为负数，则将其加上 n
  6. ch2 = ar[x2]

以下内容可能有助于解释它的工作原理。

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

a b c d e f g

c d e f g a b

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];
    }
}
我不认为这是正确的。考虑将 abcdef 向左移动 2 位，结果应该是 cdefab 而不是 cbadcf。 - Melkor
0

实际上，使用索引而不是指针是更好的方法。

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; }
0

这是我通过修改代码here得到的一个示例：

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);
}
0
这是 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);

}
0
0

有很多方法可以将数组旋转d个位置。

  1. 块交换算法。
  2. 抛球算法。
  3. 反转算法。

下面的链接来自《编程珠玑》PDF。看一下吧。用代码解释得非常清楚。

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

链接已失效。 - Haymo Kutschbach
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接