左旋转数组 C++ [英] left rotate array in place C++
问题描述
这就是我想要做的:数组 A[] = {1,2,3,4,5}向左旋转 2: A:{3,4,5,1,2}
THis is what I want to do: array A[] = {1,2,3,4,5} left rotate by 2: A:{3,4,5,1,2}
我们是否有一个简单而好的解决方案来执行此操作?我希望使用这个左旋转值更新数组 A 本身 - 没有额外的空间.
do we have a simple and good solution for doing this in place? I want the array A itself to be updated with this left rotated value - with no additional space.
我尝试了各种方法，但对于不同的测试用例，逻辑似乎不同，并且很难找到适合这个看似简单的任务的算法.
I tried various approaches but the logic seems different for various test cases and had a hard time finding one algorithm that fits for this seemingly simple task.
注意:我知道只需创建一个具有左旋转值的新数组即可轻松完成此操作.我正在尝试在输入数组本身中执行此操作.
NOTE: I know this can be easily done by just creating a new array with the left rotated values. I am trying to do this in the input array itself.
请建议.简单的伪代码应该可以.
Pls suggest. Simple pseudo code should do.
推荐答案
矢量旋转似乎是神秘算法的沃土.其中大部分都可以在野外找到，但有变化；所有高效的都需要一些思考才能了解它们的功能.
Vector rotation seems to be a particularly fertile ground for mysterious algorithms. Most of these can be found in the wild, with variations; all the efficient ones demand a bit of thought to understand their functioning.
如果你只向左旋转一个元素，你可以非常有效地做到这一点:
If you were only rotating one element to the left, you can do it extremely efficiently:
template<typename Iter>
void rotate_one(Iter first, Iter last) {
using Value = typename Iter::value_type;
if (first != last) {
Value temp = std::move(*first);
for (Iter next = std::next(first);
next != last;
first = next, next = std::next(next))
*first = std::move(*next);
*first = std::move(temp);
}
}
您可以使用它通过执行 Δ 次(更准确地说，Δ % N)来按 delta 位置旋转，但这需要时间 O(NΔ)，对于任意 Δ，这实际上是 O(N²).
You could use that to rotate by delta positions by executing it Δ times (more accurately, Δ % N), but that takes time O(NΔ), which is effectively O(N²) for arbitrary Δ.
虽然这个解决方案经常如上所示，但也可以在没有临时值对象的情况下实现它，使用交换而不是移动:
Although this solution is often shown as above, it is also possible to implement it without a temporary value object, using swaps instead of moves:
template<typename Iter>
void rotate_one(Iter first, Iter last) {
if (first != last) {
for (Iter next = std::next(first); next != last; ++first, ++next)
std::iterswap(first, next);
}
}
Swap 通常比移动要多一些工作，但可能存在一种高效的、特定于容器的交换实现.无论如何，这个版本将有助于理解以后的实现.
Swap is usually a bit more work than a move, but it is possible that there is an efficient container-specific implementation of swap. In any case, this version will help to understand a later implementation.
一个众所周知且经常被引用的 O(N) 解决方案是做三个逆向:
A well-known and often cited O(N) solution is to do three reverses:
template<typename Iter>
void rotate_one(Iter first, Iter newfirst, Iter last) {
std::reverse(first, newfirst);
std::reverse(newfirst, last);
std::reverse(first, last);
}
在我看来，这真的很优雅.您可以通过在纸上进行尝试来了解它是如何工作的:
This is really elegant, in my opinion. You can see how it works by trying it on paper:
a b ... c d w x ... y z
d c ... b a w x ... y z first rotate
d c ... b a z y ... x w second rotate
w x ... y z a b ... c d third rotate
这是众所周知的颠倒句子中单词的顺序"解决方案的一个特例，它包括首先颠倒每个单词的字母，然后颠倒整个字符串.
That's a special case of the well-known solution to "reverse the order of words in a sentence", which consists of first reversing the letters of each word, and then reversing the entire string.
但是，它存在一些问题.首先，当一次移动就足够时，它(几乎)每个元素移动两次.其次，std::reverse 需要一个双向迭代器.这没有什么问题，但如果算法与任何前向迭代器一起工作会更好.
However, it suffers from a couple of problems. First, it moves (almost) every element twice, when one move would be sufficient. Second, std::reverse requires a bidirectional iterator. There's nothing wrong with that, but it would be nicer for the algorithm to work with any forward iterator.
另一个简单的解决方案是注意，如果您使用第一种算法但使用增量为Δ而不是一个并在迭代器到达末尾时将迭代器包装回开头，那么如果 Δ ，您将正确旋转向量.和 N 互质.但是，如果它们不是素数，则您只会旋转一些元素；指数为 0 模 gcd(N, Δ) 的那些.要旋转整个向量，您需要对向量中的每个前 gcd(N, Δ) 元素执行 gcd(N, Δ) 次.
Another simple solution is to note that if you use the first algorithm but using an increment of Δ instead of one and wrap the iterators back to the beginning when they hit the end, then you will correctly rotate the vector if Δ and N are relatively prime. If they are not relatively prime, though, you will only have rotated some of the elements; the ones whose indices are 0 modulo gcd(N, Δ). To rotate the entire vector, you need to do this gcd(N, Δ) times, for each of the first gcd(N, Δ) elements in the vector.
这是一个包含 12 个元素和一个 Δ 的插图.共 3 个:
Here's an illustration with 12 elements and a Δ of 3:
a b c d e f g h i j k l
\ / / /
\/ / /
/ \ / /
/ /\ /
/ / \/
/ / / \
d b c g e f j h i a k l first loop
\ / / /
\/ / /
/ \ / /
/ /\ /
/ / \/
/ / / \
d e c g h f j k i a b l second loop
\ / / /
\/ / /
/ \ / /
/ /\ /
/ / \/
/ / / \
d e f g h i j k l a b c third loop
使用随机访问迭代器更容易(这是一个缺陷)；这是一个示例实现.(变量 count 计算已移动元素的数量；每个元素移动一次，因此当 count 达到 0 时，旋转完成.这避免了必须计算GCD 知道要运行多少次外循环.)
This is easier with random access iterators (which is a defect); here's a sample implementation. (The variable count counts the number of elements which have been moved; every element is moved once, so when count reaches 0, the rotate is complete. This avoids having to compute the GCD to know how many times to run the outer loop.)
template<typename Container>
void rotate(Container& A, typename Container::size_type delta) {
using Value = typename Container::value_type;
using Index = typename Container::size_type;
Index n = A.size();
delta %= n;
for (Index loop = 0, count = n;
count;
++loop, --count) {
Index dst = loop;
Value tmp = std::move(A[dst]);
for (Index src = loop + delta;
src != loop;
--count, dst = src, src += (src < n - delta ? delta : delta - n))
A[dst] = std::move(A[src]);
A[dst] = std::move(tmp);
}
}
如前所述，这依赖于具有随机访问迭代器的容器.
As mentioned, that relies on the container having random access iterators.
请注意，我们可以通过使用交换来消除对临时存储的需求，就像上面第一个算法的替代版本一样.如果我们这样做，那么我们就可以并行执行所有外部循环，因为它们不会相互干扰.因此，我们可以一次只向前移动一个元素，将每个元素与其 Δ-下一个对等元素交换.
Note that we could eliminate the need for the temporary storage by using swaps, as in the alternate version of the first algorithm above. If we do that, then we could just do all the outer loops in parallel, since they don't interfere with each other. So we could just move forward one element at a time, swapping each element with its Δ-next peer.
这导致了作为 std::rotate.它正好执行 N 次交换，这可能比上面的解决方案效率稍低(它执行 N + gcd(N, Δ) 移动)，但只需要前向迭代器和交换:(下面的代码稍作修改以更好地符合用上面的例子.)
That leads to the tour-de-force provided as the sample implementation of std::rotate. It does exactly N swaps, which is possibly less slightly less efficient than the solution above (which does N + gcd(N, Δ) moves), but needs only forward iterators and swaps: (The code below is slightly modified to better conform with the above examples.)
template <class Iter>
void rotate(Iter first, Iter newfirst, Iter last) {
if(first == newfirst || newfirst == last) return;
Iter next = newfirst;
do {
std::iter_swap(first++, next++);
if (first == newfirst) newfirst = next;
} while (next != last);
for(next = newfirst; next != last; ) {
std::iter_swap(first++, next++);
if (first == newfirst) newfirst = next;
else if (next == last) next = newfirst;
}
}
上述唯一棘手的部分是环绕的处理.请注意，first 和 next 之间的(循环)距离始终相同(Δ).newfirst 用于跟踪环绕点:每次first 到达newfirst，newfirst 由&Delta 推进；(通过将其分配给 next 的值，该值始终是 first 之后的 Δ).
The only tricky part of the above is the handling of wraparound. Note that the (cyclic) distance between first and next is always the same (Δ). newfirst is used to track the wraparound point: every time first reaches newfirst, newfirst is advanced by Δ (by assigning it to the value of next, which is always Δ beyond first).
next 在第一个循环结束时第一次回绕.一旦发生这种情况，它就在 Δ 之内.容器的末端；第二个循环继续交换.在这个过程中，它有效地计算了N和Δ的GCD；与欧几里得算法.
next wraps around the first time at the end of the first loop. Once that happens, it is within Δ of the end of the container; the second loop continues the swaps. In the process, it effectively computes the GCD of N and Δ with the Euclidean algorithm.
这篇关于左旋转数组 C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
