2010 年第 42 题

题目描述

设将 n 个整数存放到一维数组 R 中。请设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 p 个位置。

例如：

R = [1, 2, 3, 4, 5, 6, 7], p = 3
左移后得到 [4, 5, 6, 7, 1, 2, 3]

解题思路

最经典的原地做法是“三次翻转”。

把数组分成两段：

• 前半段：[0, p - 1]
• 后半段：[p, n - 1]

操作顺序：

1. 先翻转前半段。
2. 再翻转后半段。
3. 最后翻转整个数组。

这样就能在 O(1) 额外空间内完成循环左移。

手算示例

R = [1, 2, 3, 4, 5, 6, 7]，p = 3

原数组：
[1, 2, 3, 4, 5, 6, 7]

翻转前 3 个：
[3, 2, 1, 4, 5, 6, 7]

翻转后 4 个：
[3, 2, 1, 7, 6, 5, 4]

翻转整个数组：
[4, 5, 6, 7, 1, 2, 3]

Python 实现

def reverse(nums, left, right):
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1


def left_rotate(nums, p):
    if not nums:
        return nums

    n = len(nums)
    p %= n
    if p == 0:
        return nums

    reverse(nums, 0, p - 1)
    reverse(nums, p, n - 1)
    reverse(nums, 0, n - 1)
    return nums

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

• p 可能大于数组长度，要先做 p %= n。
• 真题是左移，和 LeetCode 189 的右移方向相反。
• 翻转区间时要确认端点是闭区间。

对应题

来源	题目	相似度	主要差异
LeetCode	189. 轮转数组	80%	真题为左旋，该题常见表述为右旋
剑指 Offer	58 - II. 左旋转字符串	90%	真题对象是数组，该题对象是字符串

难度

⭐️⭐️