1 public void rotateByOne(int[] arr) {
 2     if(arr == null || arr.length == 0){
 3         return;
 4     }
 5     int temp = arr[arr.length - 1];
 6     for(int i = arr.length - 1; i > 0; i--){
 7         arr[i] = arr[i - 1];
 8     }
 9     arr[0] = temp;
10 }

Follow up question: instead of rotating the given array by one position, rotate it by m positions, m should be controlled by

your program caller. if m is positive, it means rotating right, if m is negative, it means rotating left.

Solution 1. O(m * n) runtime

Simply call rotateByOne m times.

Solution 2. O(n) runtime, O(1) space

Algorithm: Acheive the rotation by swaping values only one time instead of m times for each location.

1. Move arr[0] to a temporary variable t, then move arr[m] to arr[0], arr[2 * m] to arr[m], and so on.(taking all indices into arr modulo arr.length), until we come back to taking the element from arr[0],

at which point we instead take t and stop the process.

2. If step 1 does not move all the elements, repeat step 1 starting from arr[1]. Repeat this step until all the elements are moved, advancing the start element to the next location each iteration.

The following code only shows the left rotation implementation, the right counter part is similar.

 1 public static void leftRotateByM(int[] arr, int m) {
 2     if(m % arr.length != 0) {
 3         int count = 0;
 4         int startIdx = 0;                   
 5         while(count < arr.length) {
 6             int currIdx = startIdx;
 7             int nextIdx = (currIdx + m) % arr.length;
 8             int temp = arr[startIdx];
 9             while(nextIdx != startIdx) {
10                 arr[currIdx] = arr[nextIdx];
11                 currIdx = nextIdx;
12                 nextIdx = (nextIdx + m) % arr.length;
13                 count++;
14             }
15             arr[currIdx] = temp;
16             startIdx++;
17             count++;
18         }
19     }
20 }

Solution 3. O(n) runtime, O(1) space, using reverse algorithm

1. decide on the split point depending if it is a left or right rotation.

2. reverse the splitted array separately, then reverse the whole array.

 1 private void reverse(int[] arr, int start, int end) {
 2     while(start < end) {
 3         arr[start] ^= arr[end];
 4         arr[end] ^= arr[start];
 5         arr[start] ^= arr[end];
 6         start++;
 7         end--;
 8     }
 9 }
10 public void rotateByMUsingReverse(int[] arr, int m) {
11     if(arr == null || arr.length == 0 || m % arr.length == 0){
12         return;
13     }
14     m %= arr.length;
15     int splitIdx = m > 0 ? arr.length - m : m;
16     reverse(arr, 0, splitIdx - 1);
17     reverse(arr, splitIdx, arr.length - 1);
18     reverse(arr, 0, arr.length - 1);
19 }

优质内容筛选与推荐>>
1、Android 亲测源码分享
2、VB批量替换文本字符
3、php soap客户端调试实例及调试
4、看单词时想到的
5、HDU 5056 Boring Count --统计

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了