Python算法题集_轮转数组

本文为Python算法题集之一的代码示例

题目189

题目：轮转数组

说明：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [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:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

- 代码分析

本题为求数组元素的移动
最笨的办法是挨个赋值，单层循环，所以基本的时间算法复杂度为（On）

- 优化思路

减少循环层次
增加分支，减少计算集合
采用内置算法来提升计算效率
分析题目特点，分析最优解

1）本题最简单的解法为数组切片连接【链表切片、连接都是（O(1)）】，但是网站不认，只能自己测

2）建立两个切片副本，循环更新元素是标准做法

3）建立数组副本，直接计算下标在循环中更新元素，减少一次切片操作

4）实施数组的反转操作，可以不用建立数据缓冲，直接完成更新

- 测量工具

CheckFuncPerf是我写的函数用时和内存占用模块，地址在这里：Python算法题集_检测函数用时和内存占用的模块【自搓】

1. 标准求解【双切片】

仅仅通过，超过12% 在这里插入图片描述

import CheckFuncPerf as cfp

def rotate_base(nums, k) :
    kx = k % len(nums)
    list1 = nums[:len(nums)-kx]
    list2 = nums[len(nums)-kx:]
    iIdx = 0
    while list2:
        nums[iIdx] = list2.pop(0)
        iIdx+=1
    while list1:
        nums[iIdx] = list1.pop(0)
        iIdx+=1
    return nums

import random
nums=[]
for iIdx in range(100000):
    nums.append(random.randint(0, 10000))
k = 1357
result = cfp.getTimeMemoryStr(rotate_base, nums, k)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 rotate_base 的运行时间为 886.20 ms；内存使用量为 860.00 KB 执行结果 = 100000

2. 改进版【数组副本+计算下标】

飞龙在天，超越97% 在这里插入图片描述

简单的改进取得97%的性能，说明本题改进的空间不大

import CheckFuncPerf as cfp

def rotate_ext1(nums, k) :
    numscopy = nums.copy()
    kx = k % len(nums)
    for iIdx in range(len(nums)):
        nums[iIdx] = numscopy[iIdx-kx]
    return nums

import random
nums=[]
for iIdx in range(100000):
    nums.append(random.randint(0, 10000))
k = 1357
result = cfp.getTimeMemoryStr(rotate_base, nums, k)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 rotate_ext1 的运行时间为 8.00 ms；内存使用量为 4.00 KB 执行结果 = 100000

3. 空间改进版【不用数据副本，三次反转】

表现优良，超越86% 在这里插入图片描述

import CheckFuncPerf as cfp

def rotate_ext2(nums, k):
    nums.reverse()
    kx = k % len(nums)
    len1, len2 = kx // 2, (len(nums)-kx) // 2
    for iIdx in range(len1):
        nums[iIdx], nums[kx-iIdx-1] = nums[kx-iIdx-1], nums[iIdx]
    for iIdx in range(len2):
        nums[kx+iIdx], nums[-iIdx-1] = nums[-iIdx-1], nums[kx+iIdx]
    return nums

import random
nums=[]
for iIdx in range(100000):
    nums.append(random.randint(0, 10000))
k = 1357
result = cfp.getTimeMemoryStr(rotate_base, nums, k)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 rotate_ext2 的运行时间为 11.99 ms；内存使用量为 0.00 KB 执行结果 = 100000

4. 王者归来【采用列表切片+合并】

网站虽然不认，还是无冕之王，管你数组多大，都只要1毫秒

import CheckFuncPerf as cfp

def rotate_ext3(nums, k):
    kx = k % len(nums)
    list1 = nums[:len(nums)-kx]
    list2 = nums[len(nums)-kx:]
    nums = list2 + list1
    return nums

import random
nums=[]
for iIdx in range(100000):
    nums.append(random.randint(0, 10000))
k = 1357
result = cfp.getTimeMemoryStr(rotate_base, nums, k)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 rotate_ext3 的运行时间为 1.00 ms；内存使用量为 792.00 KB 执行结果 = 100000