做设计在哪个网站上找高清图片大全,网站建设风险分析,玉山县建设局网站,安徽专业网站建设检修LeetCode 热题 100 | 189. 轮转数组
大家好#xff0c;今天我们来解决一道经典的算法题——轮转数组。这道题在LeetCode上被标记为中等难度#xff0c;要求我们将数组中的元素向右轮转 k 个位置。下面我将详细讲解解题思路#xff0c;并附上Python代码实现。 问题描述
给定…LeetCode 热题 100 | 189. 轮转数组
大家好今天我们来解决一道经典的算法题——轮转数组。这道题在LeetCode上被标记为中等难度要求我们将数组中的元素向右轮转 k 个位置。下面我将详细讲解解题思路并附上Python代码实现。 问题描述
给定一个整数数组 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]解题思路
核心思想 三次反转法 首先反转整个数组。然后反转前 k 个元素。最后反转剩下的 n - k 个元素。 原地操作 通过反转操作避免使用额外的空间。 Python代码实现
def rotate(nums, k):n len(nums)k k % n # 处理k大于数组长度的情况def reverse(start, end):while start end:nums[start], nums[end] nums[end], nums[start]start 1end - 1reverse(0, n - 1) # 反转整个数组reverse(0, k - 1) # 反转前k个元素reverse(k, n - 1) # 反转剩下的元素# 测试示例
nums1 [1, 2, 3, 4, 5, 6, 7]
nums2 [-1, -100, 3, 99]rotate(nums1, 3)
rotate(nums2, 2)print(nums1) # 输出: [5, 6, 7, 1, 2, 3, 4]
print(nums2) # 输出: [3, 99, -1, -100]代码解析 处理 k 大于数组长度的情况 使用 k k % n 确保 k 在数组长度范围内。 定义反转函数 reverse 函数用于反转数组中从 start 到 end 的部分。 三次反转操作 第一次反转整个数组将后 k 个元素移到前面但顺序相反。第二次反转前 k 个元素恢复其原始顺序。第三次反转剩下的 n - k 个元素恢复其原始顺序。 原地操作 直接在原数组上进行操作不需要额外的空间。 复杂度分析
时间复杂度O(n)其中 n 是数组的长度。我们只需要遍历数组三次。空间复杂度O(1)只使用了常数个额外空间。 示例运行
示例1
输入: nums [1, 2, 3, 4, 5, 6, 7], k 3
输出: [5, 6, 7, 1, 2, 3, 4]示例2
输入: nums [-1, -100, 3, 99], k 2
输出: [3, 99, -1, -100]进阶其他解法
除了三次反转法我们还可以使用其他方法解决这个问题
方法一使用额外数组
def rotate_extra(nums, k):n len(nums)k k % nrotated nums[-k:] nums[:-k]nums[:] rotated时间复杂度O(n)空间复杂度O(n)
方法二环状替换
def rotate_cyclic(nums, k):n len(nums)k k % ncount 0start 0while count n:current startprev nums[start]while True:next_idx (current k) % nnums[next_idx], prev prev, nums[next_idx]current next_idxcount 1if current start:breakstart 1时间复杂度O(n)空间复杂度O(1) 总结
通过使用三次反转法我们可以高效地将数组中的元素向右轮转 k 个位置同时保持原地操作。这种方法既简单又高效适合大多数场景。希望这篇题解对大家有所帮助如果有任何问题欢迎在评论区留言讨论
关注我获取更多算法题解和编程技巧
