力扣面试经典——189题

💡 参考代码：

/**
 * @brief 反转数组中指定范围的元素
 * 
 * @param nums 指向整型数组的指针
 * @param start 反转范围的起始索引（包含）
 * @param end 反转范围的结束索引（包含）
 * 
 * @details 使用双指针法，从两端向中间交换元素，实现数组部分反转
 *          时间复杂度: O(n)，空间复杂度: O(1)
 */
void reverse(int* nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

/**
 * @brief 将数组中的元素向右轮转 k 个位置
 * 
 * @param nums 指向整型数组的指针
 * @param numsSize 数组的长度
 * @param k 轮转的步数（非负数）
 * 
 * @details 使用三步反转法实现数组轮转：
 *          1. 反转整个数组
 *          2. 反转前 k 个元素
 *          3. 反转后 n-k 个元素
 *          
 *          例如: nums = [1,2,3,4,5,6,7], k = 3
 *          step1: [7,6,5,4,3,2,1] 反转整个数组
 *          step2: [5,6,7,4,3,2,1] 反转前3个元素
 *          step3: [5,6,7,1,2,3,4] 反转后4个元素
 *          
 *          时间复杂度: O(n)，空间复杂度: O(1)
 */
void rotate(int* nums, int numsSize, int k) {
    // 处理k大于数组长度的情况，避免不必要的轮转
    k = k % numsSize;
    
    // 三步反转法
    reverse(nums, 0, numsSize - 1);      // 反转整个数组
    reverse(nums, 0, k - 1);            // 反转前k个元素
    reverse(nums, k, numsSize - 1);     // 反转后n-k个元素
}

📖 总结：

点击展开题目总结

🤔 轮转数组

---

1️⃣ 题目核心信息

🎯 功能描述：将数组中的元素向右轮转 k 个位置，实现循环移位

📥 输入输出：

• 输入：
  • nums: 指向整型数组的指针
  • numsSize: 数组的长度
  • k: 轮转的步数（非负数）
• 输出：无返回值，直接在原数组上进行修改

---

2️⃣ 实现原理

💡 核心思路：使用三步反转法（三次数组反转）实现数组轮转

📋 实现步骤：

1. 首先对 k 取模，处理 k 大于数组长度的情况
2. 反转整个数组
3. 反转前 k 个元素
4. 反转后 n-k 个元素

---

3️⃣ 关键点解析

原始思路是模拟轮转过程，每次将数组整体右移一位，重复k次。这种方法的时间复杂度是O(n×k)，当k很大时效率较低。而最优解使用三步反转法，时间复杂度仅为O(n)。

🎯 代码技巧

• 使用取模运算 k = k % numsSize 优化轮转次数
• 采用双指针法实现数组反转，空间复杂度O(1)
• 三步反转法的巧妙应用，将轮转问题转化为反转问题

4️⃣ 使用场景

✅ 适用情况：

• 需要实现数组循环移位操作
• 对空间复杂度有严格要求的场景
• 需要原地修改数组的场合

⚠️ 前提条件：

• 数组不能为空指针
• 数组长度必须大于0
• k值必须为非负数

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n为数组长度，需要遍历数组常数次

• 💾 空间复杂度：O(1)，只使用了常数级别的额外空间

6️⃣ 注意事项

🚩 边界情况：

• k等于0或数组长度的倍数时，数组保持不变
• 数组长度为1时，无论k为何值数组都保持不变
• k大于数组长度时，需要取模运算避免多余操作

💥 易错点：

• 忘记对k取模导致不必要的计算
• 反转时边界条件处理错误
• 混淆左转和右转的方向

7️⃣ 补充说明

为什么需要 k = k % numsSize 操作？🤔

问题背景

当 k 大于数组长度时，实际上会发生重复的轮转。这个操作是为了避免不必要的重复计算。

举例说明

假设我们有一个长度为 7 的数组：[1,2,3,4,5,6,7]

k 值	实际效果	说明
k=3	[5,6,7,1,2,3,4]	轮转3步
k=10	[5,6,7,1,2,3,4]	10 = 7+3，相当于轮转3步
k=17	[5,6,7,1,2,3,4]	17 = 7×2+3，也相当于轮转3步

数学原理

对于长度为 n 的数组，轮转 k 步和轮转 k % n 步的效果完全相同。

这是因为：

• 轮转 n 步会让数组回到原始状态
• 所以轮转 k 步 = 轮转 (k/n) × n + k%n 步 = 轮转 k%n 步

优化意义

性能优化：避免不必要的重复轮转

• 如果没有取模，k=1000000时就要执行1000000次操作
• 取模后，只需要执行 1000000%7 = 2 次有效操作

结果正确性：确保算法在任何 k 值下都能正确工作

8⃣ 其他解法

✨ 环形替换法

/**
 * @brief 使用环形替换法将数组中的元素向右轮转 k 个位置
 * 
 * @param nums 指向整型数组的指针
 * @param numsSize 数组的长度
 * @param k 轮转的步数（非负数）
 * 
 * @details 核心思想是将数组中每个元素直接放到轮转后的位置上。
 *          通过追踪元素的移动轨迹形成环形，每个元素只访问一次。
 *          
 *          算法流程：
 *          1. 从每个未访问的起始位置开始
 *          2. 沿着环形路径移动元素，直到回到起始位置
 *          3. 继续处理下一个环形，直到所有元素都被处理
 *          
 *          例如: nums = [1,2,3,4,5,6], k = 2
 *          形成两个环形: 1->3->5->1 和 2->4->6->2
 *          
 *          时间复杂度: O(n)，空间复杂度: O(1)
 */
void rotate(int* nums, int numsSize, int k) {
    // 处理k大于数组长度的情况，避免不必要的轮转
    k = k % numsSize;
    
    // 记录已处理的元素个数
    int count = 0;
    
    // 遍历所有可能的起始位置，直到所有元素都被处理
    for (int start = 0; count < numsSize; start++) {
        int current = start;    // 当前处理的位置
        int prev = nums[start]; // 需要放置到下一个位置的值
        
        // 沿着环形路径移动元素，直到回到起始位置
        do {
            int next = (current + k) % numsSize;  // 计算下一个位置
            int temp = nums[next];                // 保存下一个位置的原始值
            nums[next] = prev;                    // 将prev放到下一个位置
            prev = temp;                          // 更新prev为下一个位置的原始值
            current = next;                       // 移动到下一个位置
            count++;                              // 增加已处理元素计数
        } while (start != current);  // 当回到起始位置时结束当前环形处理
    }
}

✨ 使用额外数组

/**
 * @brief 使用额外数组法将数组中的元素向右轮转 k 个位置
 * 
 * @param nums 指向整型数组的指针
 * @param numsSize 数组的长度
 * @param k 轮转的步数（非负数）
 * 
 * @details 核心思想是创建一个新数组，将原数组中每个元素直接放到轮转后的位置上，
 *          然后将新数组的内容复制回原数组。
 *          
 *          算法流程：
 *          1. 创建与原数组等长的新数组
 *          2. 遍历原数组，将每个元素 nums[i] 放到新数组的 (i + k) % n 位置
 *          3. 将新数组的内容复制回原数组
 *          
 *          例如: nums = [1,2,3,4,5,6,7], k = 3
 *          nums[0]=1 放到 newArr[(0+3)%7] = newArr[3] 的位置
 *          nums[1]=2 放到 newArr[(1+3)%7] = newArr[4] 的位置
 *          ...以此类推
 *          
 *          时间复杂度: O(n)，空间复杂度: O(n)
 */
void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];     // 创建与原数组等长的新数组
    k = k % numsSize;         // 处理k大于数组长度的情况
    
    // 将元素放到新位置
    for (int i = 0; i < numsSize; i++) {
        // 将nums[i]放到新数组的(i + k) % numsSize位置（轮转后的位置）
        newArr[(i + k) % numsSize] = nums[i];
    }
    
    // 复制回原数组
    for (int i = 0; i < numsSize; i++) {
        nums[i] = newArr[i];
    }
}

加载评论中...