#左耳听风 ARST 打卡活动重启#
目录
一、问题
二、解题方法一
三、解题方法二
四、两种方法的区别
关于 ARTS 的释义 —— 每周完成一个 ARTS:
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章
希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。
一、问题
给定一个整数数组 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]
二、解题方法一
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
nums.extend(nums[:k])
nums[:k] = nums[-k:]
这段代码实现了一个函数 `rotate`,用于将给定的整数数组 `nums` 向右轮转 `k` 个位置。
函数的输入参数有两个:
- 一个整数数组 `nums`,表示需要进行旋转操作的数组。
- 一个非负整数 `k`,表示需要向右旋转的位置数。注意,这里的 `k` 取模 `n`(即 `k % n`),因为当 `k` 大于等于 `n` 时,只需要进行一次完整的旋转即可。函数的主要思路是将数组分为两部分,前 `k` 个元素和剩余的元素,然后将这两部分分别拼接起来,得到旋转后的数组。具体实现过程如下:
1. 首先计算出数组的长度 `n`,以及对 `n` 取模的结果 `k % n`。这是因为当 `k` 大于等于 `n` 时,只需要进行一次完整的旋转即可。
2. 然后使用列表的 `extend()` 方法,在数组末尾添加前 `k` 个元素。这样就得到了一个新的数组,其中前 `k` 个元素为原数组的前半部分,剩余的元素为原数组的后半部分。
3. 最后使用列表切片的方式,将新数组中剩余的元素移动到前面,即可得到旋转后的数组。具体来说,我们可以将新数组中的第 `k` 个元素到最后一个元素取出,然后将其放到新数组的前半部分中对应的位置上。这样就可以完成整个旋转操作了。
总之,这段代码的时间复杂度为 O(n),空间复杂度为 O(1)。
三、解题方法二
另一种解题方法是使用双指针法。具体来说,我们可以定义两个指针 `left` 和 `right`,分别指向数组的开头和结尾。然后进行以下操作:
1. 将 `left` 指针向右移动 `k` 个位置,直到它指向数组的第 `k` 个元素为止。
2. 将 `right` 指针向左移动 `k` 个位置,直到它指向数组的第 `n-k` 个元素为止。
3. 将 `left` 和 `right` 指针所指向的两个元素交换位置,即可完成旋转操作。这种方法的时间复杂度为 O(n),空间复杂度为 O(1)。
文章来源地址https://www.toymoban.com/news/detail-619420.html
def rotate(nums, k):
n = len(nums)
k %= n # 对 n 取模,防止 k 大于等于 n 的情况
left, right = 0, n - 1
for _ in range(k):
temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left += 1
right -= 1
四、两种方法的区别
两种方法的区别在于,单指针法只能找到一个满足条件的元素,而双指针法则可以在 O(n) 的时间复杂度内找到所有满足条件的元素。具体来说,单指针法从数组的开头开始遍历,如果找到了一个满足条件的元素,就返回该元素的位置;否则继续向后遍历,直到遍历完整个数组。而双指针法则从数组的两端开始遍历,每次移动一个指针,当两个指针相遇时,就将它们所指向的元素交换位置。这样就可以保证每个元素都被访问过一次。 文章来源:https://www.toymoban.com/news/detail-619420.html
到了这里,关于打卡力扣题目九的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!