首页 > 代码库 > 编程之美2.17 数组循环移位
编程之美2.17 数组循环移位
问题描述:
设计一个算法,把一个含有N元素的数组循环左移或者右移K位。
解决方法:
1. 暴力解法------O(KN)
2. 颠倒位置------O(N)
具体思路和代码:
1. 暴力解法------O(KN)
思路:循环K次,每次移动一位
代码:
1 //右移 2 void s1(int A[], int n, int k) 3 { 4 k = k % n; 5 for(int i = 0; i < k; i++) 6 { 7 int t = A[n-1]; 8 for(int j = n-1; j > 0; j--) 9 { 10 A[j] = A[j-1]; 11 } 12 A[0] = t; 13 } 14 }
1 //左移 2 void s3(int A[], int n, int k) 3 { 4 k = k % n; 5 for(int i = 0; i < k; i++) 6 { 7 int t = A[0]; 8 for(int j = 1; j < n; j++) 9 { 10 A[j-1] = A[j]; 11 } 12 A[n-1] = t; 13 } 14 }
2. 颠倒位置------O(N)
思路:
例如:1 2 3 4 5 6 7 8 右移2位
3 4 5 6 7 8 1 2
我们分解下: 先对换(0, n-k-1) :1 2 3 4 5 6 -> 6 5 4 3 2 1
再对换 (n-k, n-1):7 8 -> 8 7
-> 6 5 4 3 2 1 8 7
整体对换:7 8 1 2 3 4 5 6
代码:
1 //右移 2 void reverse(int A[], int l, int r) 3 { 4 for(int i = l, j = r; i < j; i++, j--) 5 { 6 int t = A[i]; 7 A[i] = A[j]; 8 A[j] = t; 9 } 10 } 11 12 void s2(int A[], int n, int k) 13 { 14 reverse(A, 0, n-k-1); 15 reverse(A, n-k, n-1); 16 reverse(A, 0, n-1); 17 }
1 //左移 2 void s4(int A[], int n, int k) 3 { 4 reverse(A, 0, k-1); 5 reverse(A, k, n-1); 6 reverse(A, 0, n-1); 7 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。