LeetCode 189.旋转数组Python代码部分测试用例运行错误排查

问题复现 #

测试代码如下，第一个用例输出正确，第二个用例输出不符合预期：

arr = [1,2,3,4,5,6,7]
arr2 = [-1,-100,3,99]

def reverse(array, start, end):
    while start < end:
        array[start], array[end] = array[end], array[start]
        start += 1
        end -= 1
    return array

def rotate(array, k):
    reverse(array, 0, k)
    reverse(array, k+1, len(array)-1)
    reverse(array, 0, len(array)-1)
    return array


print(rotate(arr, 3))       # 输出: [5, 6, 7, 1, 2, 3, 4]，结果正确
rotate(arr2, 2)
print(arr2)                 # 输出: [99, -1, -100, 3]，预期为[3,99,-1,-100]

错误原因 #

代码存在两处逻辑问题，第一个用例运行正确属于数值巧合：

• 三次反转的区间边界完全错误
  你使用的「分段反转后整体反转」实现数组右移k位的逻辑，正确的分段规则为（n为数组长度）：
  1. 反转前半段：闭区间[0, n-k-1]，共n-k个元素
  2. 反转后半段：闭区间[n-k, n-1]，共k个元素
  3. 反转整个数组
     你当前写的反转区间是第一次反转[0, k]（共k+1个元素），第二次反转[k+1, n-1]（共n-k-1个元素），只有当k+1 = n-k也就是n=2k+1时，两段的长度才刚好和正确逻辑匹配。第一个测试用例n=7、k=3，刚好满足7=2*3+1，所以误打误撞得到正确结果；第二个测试用例n=4、k=2，不满足上述等式，分段长度完全错误，结果自然不符合预期。
     以第二个测试用例为例，你的代码执行流程为：
  4. 初始数组：[-1,-100,3,99]
  5. 反转[0,2]区间：前三个元素-1,-100,3反转为3,-100,-1，数组变为[3,-100,-1,99]
  6. 反转[3,3]区间：起止下标相同，无任何操作
  7. 反转整个数组：得到[99,-1,-100,3]，和你的错误输出完全一致。
• 未处理k的取模逻辑
  数组旋转存在周期性，当k大于等于数组长度时，有效旋转步数为k % n。你直接使用原始k作为数组下标，遇到k >= n的场景会直接触发下标越界错误。

修正后代码 #

def reverse(array, start, end):
    while start < end:
        array[start], array[end] = array[end], array[start]
        start += 1
        end -= 1
    return array

def rotate(array, k):
    n = len(array)
    k = k % n  # 计算有效旋转步数，避免k大于等于数组长度时出错
    reverse(array, 0, n - k - 1)
    reverse(array, n - k, n - 1)
    reverse(array, 0, n - 1)
    return array

修正后两个测试用例均能输出正确结果：

• 输入[1,2,3,4,5,6,7]、k=3，输出[5,6,7,1,2,3,4]
• 输入[-1,-100,3,99]、k=2，输出[3,99,-1,-100]

内容的提问来源于stack exchange，提问作者VRM