题目：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例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]
说明：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
尽量使用空间复杂度为 O(1) 的 原地 算法。
解法一：暴力法
思路分析：
遍历两次，先旋转k次，每次将数组旋转一个元素（将数组中每个元素和最后一个元素值进行交换）PHP代码实现：
/**
* @param Integer[] $nums
* @param Integer $k
* @return NULL
*/
function rotate(&$nums, $k) {
for($i=0;$i<$k;$i++){
$last = $nums[count($nums)-1];
for($j=0;$j<count($nums);$j++){
$temp = $nums[$j];
$nums[$j] = $last;
$last = $temp;
}
}
return $nums;
}使用：
$nums = [1,2,3,4,5,6,7,10];
$k = 3;
var_dump(rotate($nums,$k));复杂度分析：
时间复杂度： O(k*n)
每个元素都被移动1步:O(n）,k次:O(k)
空间复杂度： O(1)
没有额外空间被使用
当数组长度大一点时，很容易超出时间限制，明显是一个很粗暴的解决方法解法二：反转法
思路分析：
当我们旋转k次后，k%n个尾部元素会移动到数组前头，剩余的元素被往后移动
首先将所有数组反转，接着再把前k个元素反转，最后再反转后n-k个元素
假设 nums = [1,2,3,4,5,6,7] n=7 且 k=3
反转所有元素：[7,6,5,4,3,2,1]
反转前k个元素：[5,6,7,4,3,2,1]
反转后n-k个元素：[5,6,7,1,2,3,4] 此时即为结果PHP代码实现：
/**
* @param Integer[] $nums
* @param Integer $k
* @return NULL
*/
function rotate(&$nums, $k) {
$k %=count($nums);
$nums = reverse($nums,0,count($nums)-1);
$nums = reverse($nums,0,$k-1);
$nums = reverse($nums,$k,count($nums)-1);
return $nums;
}
/**
* @param $nums
* @param $start
* @param $end
* @return mixed
*/
function reverse($nums,$start,$end){
while($start<$end){
$temp = $nums[$start];
$nums[$start] = $nums[$end];
$nums[$end] = $temp;
$start++;
$end--;
}
return $nums;
}复杂度分析：
时间复杂度： O(n)
n个元素被反转了3次，即3*O(n)，还是O(n)
空间复杂度：O(1)
没有额外空间被使用解法三：环状替换
思路分析：
把数组当成环形的，把每个元素放到其后k个位置
比如[1,2,3,4,5,6,7,8]，k=2
可以把这8个元素依次放在一个八边形的各个顶点，从元素为1的顶点开始依次往前移动2个位置，最后的数组[7,8,1,2,3,4,5,6]即为结果PHP代码实现：
/**
* @param Integer[] $nums
* @param Integer $k
* @return NULL
*/
function rotate(&$nums, $k) {
$k = $k%count($nums);
$count = 0;
for($start=0;$count<count($nums);$start++){
$current = $start;//当前位置的指针
$prev = $nums[$start];
do {
$next = ($current+$k)%count($nums);
$temp = $nums[$next];
$nums[$next] = $prev;
$prev = $temp;
$current = $next;
$count++;//控制循环的次数
} while($start != $current);//开始位置和当前位置不同一个位置才进行元素移动
}
return $nums;
}复杂度分析：
时间复杂度：O(n)
只遍历了每个元素一次
空间复杂度：O(1)
使用了常数个额外空间解法四：循环遍历（k次）+哈希函数
思路分析：
先截取出前n-k个元素到一个新数组，循环遍历k次（从最后一个元素倒序遍历），把每次循环的指针位置对应的元素插到新数组前边PHP代码实现：
/**
* @param Integer[] $nums
* @param Integer $k
* @return NULL
*/
function rotate(&$nums, $k) {
$start = count($nums)-$k;
$res = array_slice($nums,0,$start);
for($i=count($nums)-1;$i>=$start;$i--){
array_unshift($res,$nums[$i]);
}
return $res;
}复杂度分析：
时间复杂度： O(n)，其中n为k
只遍历了k次
空间复杂度： O(n)
使用了新数组空间解法五：哈希函数
思路分析：
先截取出前n-k个元素到一个新数组，再截取后k个元素到另外一个新数组，最后倒序合并这两个数组即可PHP代码实现：
/**
* @param Integer[] $nums
* @param Integer $k
* @return NULL
*/
function rotate(&$nums, $k) {
$res_start = array_slice($nums,0,count($nums)-$k);
$res_end = array_slice($nums,count($nums)-$k,$k);
return array_merge($res_end,$res_start);
}复杂度分析：
时间复杂度：O(n)
空间复杂度： O(n)
使用了新数组空间github
以后每次题解都会上传到这个项目
题目来源
力扣（LeetCode）：https://leetcode-cn.com/problems/rotate-array/