Leetcode之PHP版题目解析（189. Rotate Array）

2019-3-27 星期三  开始吧

上一题链接 Leetcode之PHP版题目解析（172. Factorial Trailing Zeroes）

题目描述

给定一个数组，将数组向右旋转K步，k为非负数.返回新的数组。

题目案例

案例1给定[1,2,3,4,5,6,7],k是3，返回[5,6,7,1,2,3,4],也就是说k是多少就把数组的后k位转移到数组的前k位，形成新的数组.

题目分析

先使用php函数来实现一波，很简单的道理， 移动几个，我就从后几个删除几位，依次插入到数组的头部，两个数组函数搞定。

具体实现

/**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
        while($k>0){
              array_unshift($nums,array_pop($nums));
              $k--;
        } 
    }

解法二

我们定义一个辅助的数组，然后通过关系的映射来实现移动元素间的位置值交换。

具体实现

/**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
         $data=$nums;
         for($i=0;$i<count($nums);$i++) {
             $nums[($i+$k)% count($nums)]=$data[$i];
        }
    }

解法三

题目说让我们使用O(1)的空间完成，解法2中空间复杂度已然是O(n),所以再换一个。正如我所说的，就是后面的k个元素移到数组前面，前面的元素往后移，所以思路就是，先反转整个数组，然后反转前k个元素，最后在反转剩下的元素。

具体实现

/**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
         $k %=count($nums);
         $this->reverse($nums,0,count($nums)-1);
         $this->reverse($nums,0,$k-1);
         $this->reverse($nums,$k,count($nums)-1);
    }
    
    function reverse(&$nums,$start,$end){
        while($start<$end){
            $res=$nums[$start];
            $nums[$start]=$nums[$end];
            $nums[$end]=$res;
            $start++;
            $end--;
        }
        
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php