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
No Comments