[算法学习]数组的旋转

算法

问题描述： 返回将一维数组向右旋转k个位置的结果。
比如，一维数组{1,2,3,4,5}，k=2时，返回结果是{4,5,1,2,3}。 要求常数级空间复杂度，允许修改原有数组。

解法与分析： 使用三旋转：全部旋转一次，前面0到k-1旋转一次，后面k到数组最后一个数旋转一次，就可以解决问题。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] rotateK(int[] datas,int k)
{
    reverse(datas, 0, datas.length-1);
    reverse(datas, 0, k-1);
    reverse(datas,k,datas.length-1);
    return datas;
}

/**
 * 反转start和end之间的数
 * @param datas
 * @param start
 * @param end
 */
public static void reverse(int[] datas,int start,int end)
{
    while(start<end)
    {
        // 交换两个数的值
        datas[start]^=datas[end];
        datas[end]^=datas[start];
        datas[start]^=datas[end];
        start++;
        end--;
    }
}