每日一道算法：旋轉數組

題目：給定一個數組，将數組中的元素向右移動 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] 此時即為結果           

/**
 * @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]即為結果           

/**
 * @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次（從最後一個元素倒序周遊），把每次循環的指針位置對應的元素插到新數組前邊           

/**
 * @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個元素到另外一個新數組，最後倒序合并這兩個數組即可           

/**
 * @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_PHP：https://github.com/zhangdejian/LeetCode_PHP

題目來源

力扣（LeetCode）： https://leetcode-cn.com/problems/rotate-array/