示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
第一种暴力法：
public static void rotate1(int[] arr,int k) {
//对k做处理，确定移动几次
k %= arr.length;
while(k>0) {
//将最后一个元素赋给临时变量
int tmp = arr[arr.length - 1];
//从下标arr.length - 1开始，将前一个位置的元素赋给后一个位置
for(int i = arr.length - 1;i>0;i--) {
arr[i] = arr[i - 1];
}
//最后将最后一个元素赋给第一个元素
arr[0] = tmp;
k--;
}
}
第二种：逆序法
public static void rotate2(int[] arr,int k) {
//确定移动次数
k %= arr.length;
//将整个数组逆序
reserve(arr,0,arr.length - 1);
//将前k个逆序
reserve(arr,0,k-1);
//从下标k到数组长度之间逆序
reserve(arr,k,arr.length - 1);
}
//逆序
public static void reserve(int[] arr,int start,int end) {
while(start < end) {
int tmp = arr[end];
arr[end--] = arr[start];
arr[start++] = tmp;
}
}