开发者社区> 张德Talk> 正文

每日一道算法:旋转数组

简介: 每天一道算法题,可以让自己的思维和深度慢慢无限延伸。
+关注继续查看

题目:给定一个数组,将数组中的元素向右移动 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_PHP:https://github.com/zhangdejian/LeetCode_PHP

题目来源

力扣(LeetCode):https://leetcode-cn.com/problems/rotate-array/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2349 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14318 0
☆打卡算法☆LeetCode 48、旋转图像 算法解析
“给定一个二维矩阵表示一个图像,将图像顺时针旋转90°,返回旋转后的图像矩阵。”
14 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
30126 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
14039 0
经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)
题目 Assume you have a method isSubstring which checks if one word is a substring of another.
844 0
图像处理之图像快速旋转算法
基本思想: 旋转矩阵在旋转角度较小的情况下可以通过两次错切变化得到旋转效果的图片,在旋 转角度较大的情况下可以通过三次错切得到等价旋转效果图像(较小角度小于15度,较 大角度在90度之内),对于旋转角度超过90度,首先旋转特殊角度90,180,270,然后 在旋转剩下的角度数。
1164 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
21210 0
+关注
张德Talk
每日精进,致力于全栈工程师!
24
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载