IT评测·应用市场-qidao123.com

标题: LeetCode hot 100 逐日一题(11)——189. 轮转数组 [打印本页]

---

作者: 不到断气不罢休    时间: 2025-3-24 11:39
标题: LeetCode hot 100 逐日一题(11)——189. 轮转数组
这是一道难度为中等的标题，让我们来看看标题描述：
   给定一个整数数组 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]
  

---

  提示：
  

• 1 <= nums.length <=                                              1                                           0                                  5                                                 10^5                        105
  
•                                              −                                           2                                  31                                                 -2^{31}                        −231 <= nums <=                                                          2                                  31                                                 2^{31}                        231 - 1
  
• 0 <= k <=                                              1                                           0                                  5                                                 10^5                        105
  

  题解

1. class Solution {
2.     public void rotate(int[] nums, int k) {
3.         int n = nums.length;  // 获取数组的长度
4.         k %= n;  // 取模运算，防止 k 超过数组长度（若 k == n，则轮转后数组不变）
6.         // 1. 先整体翻转数组
7.         reverse(nums, 0, n - 1);
9.         // 2. 翻转前 k 个元素，使其恢复正确顺序
10.         reverse(nums, 0, k - 1);
12.         // 3. 翻转剩余的 n-k 个元素，使其恢复正确顺序
13.         reverse(nums, k, n - 1);
14.     }
16.     // 反转数组的辅助方法
17.     private void reverse(int[] nums, int i, int j) {
18.         while (i < j) {  // 采用双指针法，交换 i 和 j 位置的元素
19.             int temp = nums[i];
20.             nums[i++] = nums[j];  // i 向右移动
21.             nums[j--] = temp;  // j 向左移动
22.         }
23.     }
24. }

复制代码

算法思路

使用 三次翻转 解决数组的右移问题：

• 团体翻转数组（第一次翻转）：把数组 [1,2,3,4,5,6,7] 变成 [7,6,5,4,3,2,1]。
  
• 翻转前 k 个元素（第二次翻转）：将 [7,6,5] 翻转后变为 [5,6,7]，其余部门 [4,3,2,1] 保持稳定。
  
• 翻转剩余部门（第三次翻转）：将 [4,3,2,1] 翻转后变为 [1,2,3,4]。
  

最终得到正确的 右移 k 次后的数组。
示例演示

示例 1:

1. 输入: nums = [1,2,3,4,5,6,7], k = 3

复制代码

执行 rotate(nums, 3)：

• 团体翻转: [7,6,5,4,3,2,1]
  
• 翻转前 3 个元素: [5,6,7,4,3,2,1]
  
• 翻转剩余部门: [5,6,7,1,2,3,4]
  

最终输出：[5,6,7,1,2,3,4]
时间复杂度分析

• 数组翻转的时间复杂度：
  
  
  
  • 第一次翻转: O(n)
    
  • 第二次翻转: O(k)
    
  • 第三次翻转: O(n-k)
    
  
  

总时间复杂度为 O(n)，相比于暴力解法（O(n × k)）更高效。
空间复杂度分析

• 只使用了 常数级额外空间（int temp 变量），因此 空间复杂度为 O(1)。
  

问题与解答

   [NOTE] 问题1
k %= n; // 取模运算，防止 k 超过数组长度（若 k == n，则轮转后数组稳定）这一句中，如果k超过数组长度会怎么样？如果k为n+1呢？
解答：
情况分析
如果 k 直接超过数组长度 n，那么我们实际上只关心 k % n 的结果，而不是 k 的实际值。
示例 1
  假设数组 nums = [1,2,3,4,5]，n = 5：
  

• 若 k = 5，k % 5 = 0，意味着数组轮转 5 次后回到原始状态。
  
• 若 k = 6，k % 5 = 1，意味着 轮转 6 次 = 轮转 1 次，即 [5,1,2,3,4]。
  
• 若 k = 10，k % 5 = 0，数组轮转 10 次后仍然保持稳定。
  
• 若 k = n + 1 = 6，k % 5 = 1，等效于 k = 1 的情况。
  

  一样寻常规律
  

• 由于数组是 循环布局，当 k 大于等于 n 时，多出来的 n 轮转不会改变最闭幕果，因此 k % n 取余数是关键。
  
• 代码中的 k %= n; 保证 k 永久在 [0, n-1] 范围内，不会导致重复盘算，使算法更高效。
  

    [NOTE] 问题2

1. while (i < j) {  // 采用双指针法，交换 i 和 j 位置的元素
2.             int temp = nums[i];
3.             nums[i++] = nums[j];  // i 向右移动
4.             nums[j--] = temp;  // j 向左移动
5.         }

复制代码

这段双指针法交换位置是否可以作为模板使用？
解答：
双指针法（Two Pointers）详解
概念
  

• 双指针法 是一种 高效的 处理惩罚 数组翻转（大概部门翻转）的方式。
  
• 接纳 左右两端同时交换 的方式，可以 一次遍历 完成数组反转。
  
• 时间复杂度：O(n)，空间复杂度：O(1)。
  示例演示
  假设：
  nums = [1, 2, 3, 4, 5]
  

  执行 reverse(nums, 0, 4);，即反转整个数组。
  迭代过程
  迭代次数ijnumsnums[j]交换后数组初始状态0415[5,2,3,4,1]第 1 次迭代1324[5,4,3,2,1]第 2 次迭代2233[5,4,3,2,1]（中点，稳定）  

• 终止条件: i >= j 时制止，即遍历到数组中心即可完成反转。
  

  

---

  作为模板使用该方法可用于以了局景
  

• 翻转整个数组
  reverse(nums, 0, nums.length - 1);
  适用于 数组翻转、字符串翻转 等。
  
• 翻转子数组
  reverse(nums, left, right);
  适用于 局部翻转、K 轮转 等问题，如 字符串中的单词反转。
  
• 查抄是否为回文
  

1. boolean isPalindrome(String s) {
2.    int i = 0, j = s.length() - 1;
3.    while (i < j) {
4.        if (s.charAt(i++) != s.charAt(j--)) return false;
5.    }
6.    return true;
7. }

复制代码

适用于 判定字符串或数组是否对称。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4