力扣(leetcode)-初级算法
轮转数组-做题思路与解法解析
示例一:
输入: 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]
示例二:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
现在我们来看这道题。
def main(nums,k): for i in range(k): temp=nums[-1]#将列表最后一个元素存在temp因为每一步都是将列表最后一个元素移到列表的第一位,其余的往右边移动一位 for j in range(len(nums)-2,-1,-1):#从倒数第二个元素,到第0个元素,进行循环 nums[j+1]=nums[j]#将每个元素向右移动一位 nums[0]=temp#将列表最后一位元素移到第一位
时间复杂度O(k*n)
这样思路是正确的,但是由于时间复杂过大,所以在运行时超时了,呜呜呜呜......
k %= len(nums)取余是方便当k大于列表的长度的计算 nums[:] = nums[-k:]+nums[:-k]#加一个列表的浅拷贝
时间复杂度O(n-k)(这个我也不太确定,列表切片的时间复杂度应该时O(K),k代表切片中元素的个数)
for i in range(len(nums)): lists.append(nums[i])#复制列表 for i in range(len(nums)): nums[(i+k)%len(nums)]=lists[i]#旋转列表
时间复杂度O(n)
空间复杂度O(n)
后续有新方法会更新
未完待续中.......
题目链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/