C / C ++-在不使用内置函数的情况下旋转数组的有效方法(作业) [英] C/C++ - efficient method of rotating an array without using build-in functions (homework)
问题描述
任务是向左旋转或向右旋转给定次数的数组子数组。
The task is to rotate left or rotate right a subarray of an array given number of times.
让我在一个示例中对此进行解释:
Let me explain this on an example:
- 让数据成为数组。
data = {0,1,2,3,4,5,6,7,8,9};
data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- 子数组由参数begin和end决定。
如果begin = 3和end = 7,则子数组为{0,1,2, 3,4,5 ,6,7, 8,9};
if begin = 3 and end = 7, then subarray is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
如果begin = 7且end = 3,则子数组为{ 0,1,2 ,3 ,4、5、6, 7、8、9 };
if begin = 7 and end = 3, then subarray is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- 向右旋转两次
如果begin = 3和end = 7,则结果为{0,1,2, 6、7、3、4、5, 8、9};
if begin = 3 and end = 7, then the result is {0, 1, 2, 6, 7, 3, 4, 5, 8, 9};
如果begin = 7且end = 3,则结果为{ 8、9、0、1,,4、5、6, 2、3、7 };
if begin = 7 and end = 3, then the result is {8, 9, 0, 1,, 4, 5, 6, 2, 3, 7};
我已经编写了执行此任务的代码,但速度很慢。
有人可以提示我如何使其更快吗?
重要提示:除数据,子程序和内置函数外,不允许使用其他数组。
I've written code that performs this task but it's to slow. Can someone give me a hint how to make it quicker? Important: I'm not allowed to use other arrays than data, subprograms and build-in functions.
#include <iostream>
using namespace std;
int main(){
int dataLength;
cin >> dataLength;
int data [ dataLength ];
for (int i = 0; i < dataLength; i++){
cin >> data [ i ];
}
int begin;
int end;
int rotation;
int forLoopLength;
int tempBefore;
int tempAfter;
cin >> begin;
cin >> end;
cin >> rotation;
if (end > begin)
forLoopLength = (end - begin) + 1;
else
forLoopLength = (end - begin) + 1 + dataLength;
if (rotation < 0)
rotation = forLoopLength + (rotation % forLoopLength);
else
rotation = rotation % forLoopLength;
for (int i = 0; i < rotation; i++) {
tempBefore = data [ end ];
for (int i = 0; i < forLoopLength; i++) {
tempAfter = data [ (begin + i) % dataLength ];
data [ (begin + i) % dataLength ] = tempBefore;
tempBefore = tempAfter;
}
}
for (int i = 0; i < dataLength; i ++ ) {
cout << data [ i ] << " ";
}
return 0;
}
推荐答案
这有一个窍门。如果在课堂上没有提到这个技巧,您会把它当作家庭作业是很奇怪的。无论如何...
There's a trick to this. It's pretty weird that you'd get this for homework if the trick wasn't mentioned in class. Anyway...
要旋转M留下的N个元素的序列:
To rotate a sequence of N elements left by M:
- 反转整个序列
- 反转最后M个元素
- 反转第一个NM元素
完成
例如由2留下:
1234567
->
7654321
->
7654312
->
3456712
e.g. left by 2: 1234567 -> 7654321 -> 7654312 -> 3456712
这篇关于C / C ++-在不使用内置函数的情况下旋转数组的有效方法(作业)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!