python动态数组原理(Python实现的旋转数组功能算法示例)
python动态数组原理
Python实现的旋转数组功能算法示例本文实例讲述了Python实现的旋转数组功能算法。分享给大家供大家参考,具体如下:
一、题目
给定一个数组,将数组中的元素向右移动 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]
说明:
1.尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
2.要求使用空间复杂度为 O(1) 的原地算法。
二、解法
解法一
以倒数第 k 个值为分界线,把 nums 截成两组再组合。因为 k 可能大于 nums 的长度(当这两者相等的时候,就相当于 nums 没有移动),所以我们取 k % len(nums)
,k 和 nums 的长度取余,就是最终我们需要移动的位置
代码如下:
|
if nums: k = k % len (nums) nums[:] = nums[ - k:] + nums[: - k] |
时间:64ms,击败了98%
附:本机测试示例代码:
|
# -*- coding:utf-8 -*- nums = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] k = 3 if nums: k = k % len (nums) nums[:] = nums[ - k:] + nums[: - k] print (nums) |
运行结果:
[5, 6, 7, 1, 2, 3, 4]
解法二
先把 nums 最后一位移动到第一位,然后删除最后一位,循环k次。k = k % len(nums)
,取余
代码如下:
|
if nums: k = k % len (nums) while k > 0 : k - = 1 nums.insert( 0 , nums[ - 1 ]) nums.pop() |
时间:172ms,击败了16%
附:本机测试示例代码:
|
# -*- coding:utf-8 -*- nums = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] k = 3 if nums: k = k % len (nums) while k > 0 : k - = 1 nums.insert( 0 , nums[ - 1 ]) nums.pop() print (nums) |
运行结果:
[5, 6, 7, 1, 2, 3, 4]
解法三
先把 nums 复制到 old_nums ,然后 nums 中索引为 x 的元素移动 k 个位置后,当前索引为 x+k,其值为 old_nums[x]
。,所以我们把 x+k 处理成 (x+k)%len(nums)
,取余操作,减少重复的次数。
代码如下:
|
if nums: old_nums = nums[:] l = len (nums) for x in range (l): nums[(x + k) % l] = old_nums[x] |
时间:64ms,击败了98%
附:本机测试示例代码:
|
# -*- coding:utf-8 -*- nums = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] k = 3 if nums: old_nums = nums[:] l = len (nums) for x in range (l): nums[(x + k) % l] = old_nums[x] print (nums) |
运行结果:
[5, 6, 7, 1, 2, 3, 4]
希望本文所述对大家Python程序设计有所帮助。
原文链接:https://blog.csdn.net/linfeng886/article/details/81981192
- python3 for循环怎么用(Python3.5基础之变量、数据结构、条件和循环语句、break与continue语句实例详解)
- kmp算法怎么用c描述(详解小白之KMP算法及python实现)
- python图片aes加密(python实现AES加密和解密)
- python企业微信录信息(python获取微信企业号打卡数据并生成windows计划任务)
- python中查看数据类型的内置函数(python学习——内置函数、数据结构、标准库的技巧推荐)
- python 从入门到实践笔记(python基础梳理一推荐)
- python的decode函数在哪个模块(python中报错"json.decoder.JSONDecodeError: Expecting value:"的解决)
- python中的reload(搞清楚 Python traceback的具体使用方法)
- centos7上安装python(centos6.5安装python3.7.1之后无法使用pip的解决方案)
- python自动计算机器人(python实现nao机器人手臂动作控制)
- centos8配置python开发环境(CentOS6.9 Python环境配置python2.7、pip、virtualenv)
- python3.9.6生成的注册表(厉害了,Python也能操作注册表)
- python菜单栏教程(Python3.5实现的三级菜单功能示例)
- python开发网站github(使用 Python 玩转 GitHub 的贡献板推荐)
- 如何用python做一个弹窗(python实现弹窗祝福效果)
- python3和python2 兼容(Python2和Python3的共存和切换使用)
- 挑战新国标电自天花板,九号机械师MMAX 110P深度体验(挑战新国标电自天花板)
- 《满江红》不要只当电影看,学生应该这样做(满江红不要只当电影看)
- 电影《民间怪谈录之走阴人》定档8月5日,开启一场中式惊悚之旅(电影民间怪谈录之走阴人定档8月5日)
- 原创图画书,以儿童视角讲述中国故事(以儿童视角讲述中国故事)
- 八月再见 愿你岁月不扰,余生静好(八月再见愿你岁月不扰)
- 赏读 八月再见,九月你好(赏读八月再见九月你好)
热门推荐
- pythonfor循环如何遍历嵌套列表(在Python中,不用while和for循环遍历列表的实例)
- mysql mvcc 流程(Mysql MVCC机制原理详解)
- sql server中dense_rank和row_number的区别
- php抽奖功能(php+lottery.js实现九宫格抽奖功能)
- sql性能优化案例(SQL性能优化之定位网络性能问题的方法DEMO)
- laravel请求处理流程(详解如何实现Laravel的服务容器的方法示例)
- python带权限复制文件夹(python定时复制远程文件夹中所有文件)
- 网站测试包括哪些内容
- 日常操作docker命令(Docker常用命令详解)
- js对日期加减指定天、时、分、秒
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9