专栏首页python3Python3实现旋转数组的3种算法

Python3实现旋转数组的3种算法

下面是python3实现的旋转数组的3种算法。 一、题目 给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。 例如: 输入: [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] 说明: 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 假设: nums= [1,2,3,4,5,6,7] k =3 运行结果: [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 假设: nums= [1,2,3,4,5,6,7] k =3 运行结果: [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 假设: nums= [1,2,3,4,5,6,7] k =3 运行结果: [5, 6, 7, 1, 2, 3, 4]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python实现给定一个数和数组,求数组

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    用户2398817
  • python(leetcode)-1.两

    分析原因:代码两层for循环,时间复杂度为O(n^2),所以遇到数据量大的情况耗时较久。

    用户2398817
  • leetCode

    Given an array of integers, return indices of the two numbers such that they add...

    用户2398817
  • LeetCode 280. Wiggle Sort IIsolution

    复杂度 时间 O(N) 空间 O(1) 思路 题目对摇摆排序的定义有两部分: 如果i是奇数,nums[i] >= nums[i - 1] 如果i是偶数...

    desperate633
  • LeetCode 16 3Sum Closest

    ShenduCC
  • python实现给定一个数和数组,求数组

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    用户2398817
  • 283 Move Zeroes

    /** * 题意:将0挪到末尾,并且不改数组中原有元素的顺序 * 解析:找到0元素,然后寻找其后面非0的元素,进行交换位置 * @param {numbe...

    用户1624346
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • LeetCode-31-Next-Permutation

    这个排序主要是有两种情况,一个是类似于3 1 2这样的情况,直接从后往前找到第一个nums[i]<nums[i-1]的,然后把i记下来,再与后面第一个小于i的k...

    小二三不乌
  • LeetCode-15-3Sum&&4Sum

    同之前的2sum差不多,计算两个的和的方式是:为了避免重复,重新用一个set容器,解决重复的问题。但是这里的情况是,重复的一个数字是可以出现的,而且是三个数字相...

    小二三不乌

扫码关注云+社区

领取腾讯云代金券