如何从左到右和从右到左遍历数组
发布网友
发布时间：2022-04-24 06:49
共1个回答
热心网友
时间：2022-06-17 04:14
#include <iostream>
#include <iterator>
#include <algorithm>
size_t *(size_t m, size_t n)
{
return n==0 ? m : *(n, m % n);
}
void rotate(int *arr, size_t n, int k) // n:数组长度， k:右移位数
{
size_t d = *(n, (k>0 ? k: -k)); // 获得n和|k|的最大公约数
for (size_t i = 0; i < d; i++)
{
int tmp = arr[i];
size_t prev_pos = i;
size_t cur_pos = prev_pos;
while ((prev_pos = (prev_pos+n-k)%n) != i)
{
arr[cur_pos] = arr[prev_pos];
cur_pos = prev_pos;
}
arr[cur_pos] = tmp;
}
}
// 测试代码
int main()
{
using std::copy;
using std::ostream_iterator;
using std::cout;
using std::endl;
const size_t SIZE = 18;
const int RIGHT = 12;
int arr[SIZE];
for (int i = 0; i < SIZE; i++)
arr[i] = i;
rotate(arr, SIZE, RIGHT);
copy(arr, arr+SIZE, ostream_iterator<int>(cout, " "));
system("pause");
}
对于可随机访问的数组,有比三次convert更快的算法,如上所示(STL中对Random Access Iterator即使用此算法).
LZ的算法与此相同,只不过不需要check.数学上可以证明只要循环*(n,k)次就可遍历所有元素恰好一次.
该算法的时间复杂度为n+*(n,k),即每个数组元素恰好赋值一次,每个循环需有一次临时变量的赋值.
