旋转数组

一. 题目

将包含* n* 个元素的数组向右旋转 *k *步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意:

尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

提示:

要求空间复杂度为 O(1)

二. 思路：

在length-k位置将数组分为两部分，前后分别转置，再整体转置。
具体例子：
arr = 1 2 3 4 5 6 7
k = 3
从5开始分界
前边转置为4 3 2 1
后边转置为7 6 5
这时整体为4 3 2 1 7 6 5
再整体转置一次：5 6 7 1 2 3 4

三. AC代码

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
      //测试
    public static void main(String[] args) {
        Scanner scnaner = new Scanner(System.in);
        Solution solution = new Solution();
        int n,k;
        int[] arr;
        while(scnaner.hasNext()) {
            n = scnaner.nextInt();
            k = scnaner.nextInt();
            arr = new int[n];
            for(int i = 0; i < n; i++)
                arr[i] = scnaner.nextInt();
            solution.rotate(arr,k);
            System.out.println(Arrays.toString(arr));
        }       
    }


    public void rotate(int[] nums, int k) {
        if(k <= 0) return;                                             //考虑k <= 0的情况
        int n = nums.length - (k % nums.length);  //考虑k > nums.length的情况
        reverse(nums,0,n-1);
        reverse(nums,n,nums.length - 1);
        reverse(nums,0,nums.length - 1);
    }

    private void reverse(int[] nums,int l,int r) {
        if(l < 0 || l >= nums.length || r < 0 || r >= nums.length) return;
        int i = l,j = r;
        int tmp;
        while(i < j) {
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
}