C++实现一维向量旋转算法

在C++编程中，一维向量旋转算法是一种常见的数据操作，特别是在处理数组或序列数据时。这种算法的主要目的是改变一维数组或向量的顺序，使得某些元素按照特定规则移动。在给定的场景中，我们需要将一个一维向量向左旋转指定的位数，即原向量的元素向左移动，最左边的元素移动到向量的末尾。 我们来看一种直观的解决方案，即思路一。这种方法是通过创建一个临时数组来存储向量的前i个元素，然后将剩余元素左移i个位置，最后将临时数组的元素放回原向量的末尾。这种方法虽然简单易懂，但缺点是它需要额外的空间存储i个元素，当i接近向量长度n时，空间复杂度会达到O(n)。 ```cpp string tmp(s, 0, i); // 保存前i个元素 for(int j=i; j<s.size(); ++j) { s[j-i] = s[j]; // 剩余元素左移 } s = s.substr(0, s.size()-i) + tmp; // 把tmp放回原向量末尾 ``` 思路二是通过定义一个函数，该函数将向量向左旋转一个位置，然后重复调用这个函数i次。这种方法的空间复杂度是O(1)，因为没有使用额外的数组，但它的运行时间会增加，因为每个旋转操作都需要遍历整个向量，所以总的时间复杂度为O(n * i)。 ```cpp void rotateOnce(string &s) { char tmp = s[0]; for(int i=1; i<s.size(); ++i) { s[i-1] = s[i]; } s[i-1] = tmp; } // 调用rotateOnce函数i次 while(i--) { rotateOnce(s); } ``` 思路三是利用数学技巧，即欧几里得除法和最大公约数（GCD）的概念。这种方法通过每次交换元素，逐步将x[0]移动到正确的位置，同时避免了创建额外的数组。这种方法的空间复杂度是O(1)，并且在执行i次旋转时，总时间复杂度接近O(n)。具体的实现涉及到计算i和n的最大公约数，然后根据这个值进行循环交换元素。 ```cpp int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } void rotateByGCD(string &s, int i, int n) { int g = gcd(i, n); for (int j = 0; j < g; ++j) { char t = s[j]; int k = j; while (true) { int next = k + i; if (next >= n) next -= n; if (next == j) break; s[k] = s[next]; k = next; } s[k] = t; } } // 调用rotateByGCD函数 rotateByGCD(s, i, s.size()); ``` 总结来说，一维向量旋转算法有多种实现方式，每种方式都有其时间和空间效率的权衡。在实际应用中，需要根据具体需求选择合适的策略，比如在内存有限的情况下，可能需要牺牲一些运行时间；而在运行时间有限的情况下，可能需要接受更多的内存开销。理解和掌握这些算法可以帮助我们在编程时做出更优化的选择。