旋转数组问题求解

旋转数组

将包含 n 个元素的数组向右旋转 k 步。

例如，如果  n = 7 ,  k = 3，给定数组[1,2,3,4,5,6,7]，向右旋转后的结果[5,6,7,1,2,3,4]。

解法一：

 可以每次将数组中的元素右移一位，循环K次。由于向右旋转位数k可能大于数组元素个数n,所以通用的规律是：右移位数k=k%n。

void rotate(vector<int>& nums, int k) {
if (nums.empty() == 1 || nums.size() == 1)
return;
size_t n = nums.size();
while (k--) {
int temp = nums[n - 1];
for (int i = n - 1; i > 0; --i) {
nums[i] = nums[i - 1];
}
nums[0] = temp;
}
}
int main()
{
vector<int> v = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};//16
rotate(v, 3);
for (auto i : v)
cout << i << " ";
cout << endl;
system("pause");
return 0;
}

解法二：（打死都想不出的方法）

假设一个数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：

（1）逆序排列abcd：abcd1234 → dcba1234；

（2）逆序排列1234：dcba1234 → dcba4321；

（3）全部逆序：dcba4321 → 1234abcd。

再看一个例子：向右旋转k步，就把数组中最后的k个元素按照原来的顺序移到前面，把前面的移到后面。

void rotate(vector<int>& nums, int k,int i,int j) {
for (; i < j; ++i, --j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
int main()
{
vector<int> v = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};//16
size_t n = v.size();
int i = v.front();
int j = v.back();
int k;
cout << "请输入旋转步数：";
cin >> k;
k = k%n;
rotate(v, 3, 0, n-k-1);
rotate(v, 3, n - k, n - 1);//这是后面的k个元素
rotate(v, 3, 0, n - 1);
for (auto i : v)
cout << i << " ";
cout << endl;
system("pause");
return 0;
}

最后

以上就是友好秀发为你收集整理的旋转数组问题求解的全部内容，希望文章能够帮你解决旋转数组问题求解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。