题目描述

轮转数组：给定一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负整数。例如，数组 [1, 2, 3, 4, 5] 向右轮转 2 个位置后，应变为 [4, 5, 1, 2, 3]。

示例

输入：nums = [1, 2, 3, 4, 5], k = 2 输出：[4, 5, 1, 2, 3]

解题思路

1. 暴力解法：直接通过多次交换元素位置来实现，但这种方法的时间复杂度较高，为 O(n*k)。
2. 三次反转法：
   • 首先，将整个数组反转。
   • 然后，分别反转数组的前 k % n 个元素和剩余的元素（因为轮转可能超过数组长度，需要取模）。这种方法的时间复杂度为 O(n)。

示例代码

PHP

function rotate(array &$nums, $k) {
    $n = count($nums);
    $k = $k % $n; // 如果k大于数组长度，取模
    
    // 反转整个数组
    reverse($nums, 0, $n - 1);
    // 反转前k个元素
    reverse($nums, 0, $k - 1);
    // 反转剩余元素
    reverse($nums, $k, $n - 1);
}

function reverse(&$nums, $start, $end) {
    while ($start < $end) {
        $temp = $nums[$start];
        $nums[$start] = $nums[$end];
        $nums[$end] = $temp;
        $start++;
        $end--;
    }
}

// 示例
$nums = [1, 2, 3, 4, 5];
$k = 2;
rotate($nums, $k);
print_r($nums);

Python

def rotate(nums, k):
    n = len(nums)
    k = k % n  # 如果k大于数组长度，取模
    
    # 反转整个数组
    nums.reverse()
    # 反转前k个元素
    nums[:k] = reversed(nums[:k])
    # 反转剩余元素
    nums[k:] = reversed(nums[k:])

# 示例
nums = [1, 2, 3, 4, 5]
k = 2
rotate(nums, k)
print(nums)

注意：Python 中的 reversed() 函数返回一个迭代器，这里通过切片赋值的方式直接反转了列表的指定部分。

JavaScript

function rotate(nums, k) {
    const n = nums.length;
    k = k % n; // 如果k大于数组长度，取模
    
    // 反转整个数组
    reverse(nums, 0, n - 1);
    // 反转前k个元素
    reverse(nums, 0, k - 1);
    // 反转剩余元素
    reverse(nums, k, n - 1);
}

function reverse(nums, start, end) {
    while (start < end) {
        let temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

// 示例
let nums = [1, 2, 3, 4, 5];
let k = 2;
rotate(nums, k);
console.log(nums);

这些代码示例展示了如何使用三次反转法来高效地解决轮转数组的问题。在码小课网站上，你可以找到更多关于算法和数据结构的深入解析和练习。