题目
设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度位O(N)，且只允许使用俩个附加变量。
分析
暴力法
不考虑复杂度要求，我们可以写出双层循环的代码。
时间复杂度O(len*pos);使用了三个附加变量i、j、tmp
C
#include<stdio.h> int* RighShift(int* n, int len, int pos)//右移函数 { int i = 0; int j = 0; pos = pos % len;//防止pos超过数组长度 for (i = 0; i < pos; i++)//右移pos轮 { int tmp = n[len - 1]; for (j = len - 1; j >= 0; j--)//每轮交换len-1次 { n[j] = n[j - 1]; } n[0] = tmp; } return n; } void PrintInt(int* n, int len)//输出数组的元素 { int i = 0; for (i = 0; i < len; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = { 1,2,3,4,5,6 }; int pos = 3; int len = sizeof(n) / sizeof(n[0]); RighShift(n, len, pos); PrintInt(n, len); return 0; }
三次反转法
第一次将数组全部元素前后反转。
第二次将数组[0,pos-1]范围的元素前后反转
第三次将数组[pos,len-1]范围的元素前后反转。如下图
具体实现如下
C
#include<stdio.h> void swap(int* n, int front, int later)//交换函数 { int tmp = n[front]; n[front] = n[later]; n[later] = tmp; } int* RighShift(int* n, int len, int pos)//右移函数 { int i = 0; pos = pos % len; for (i = 0; i < (len >> 1); i++)//第一次交换 { swap(n, i, len - 1 - i); } for (i = 0; i < (pos >> 1); i++) { swap(n, i, pos - 1 - i); } for (i = pos; i < ((pos + len) >> 1); i++) { swap(n, i, len - 1 - (i - pos)); } return n; } void PrintInt(int* n, int len)//输出数组的元素 { int i = 0; for (i = 0; i < len; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = { 1,2,3,4,5,6 }; int pos = 3; int len = sizeof(n) / sizeof(n[0]); RighShift(n, len, pos); PrintInt(n, len); return 0; }
这次代码已经符合题目要求了，时间复杂度为O(N),附加变量有tmp和i。但是还可以优化代码将三次for循环写成一个反转函数。优化如下
C
#include<stdio.h> void swap(int* n, int front, int later)//交换函数 { int tmp = n[front]; n[front] = n[later]; n[later] = tmp; } void Reverse(int* n, int start, int end)//反转函数 范围[start, end); { int i = 0; for(i = start; i < (start + end) >> 1; i++) { swap(n, i, end - 1 - (i - start)); } } int* RighShift(int* n, int len, int pos)//右移函数 { pos = pos % len; Reverse(n, 0, len); Reverse(n, 0, pos); Reverse(n, pos, len); return n; } void PrintInt(int* n, int len)//输出数组的元素 { int i = 0; for (i = 0; i < len; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = { 1,2,3,4,5,6 }; int pos = 3; int len = sizeof(n) / sizeof(n[0]); RighShift(n, len, pos); PrintInt(n, len); return 0; }
本章完！
