这是一道难度为中等的标题，让我们来看看标题描述：
给定一个整数数组 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
题解
- class Solution {
- public void rotate(int[] nums, int k) {
- int n = nums.length; // 获取数组的长度
- k %= n; // 取模运算，防止 k 超过数组长度（若 k == n，则轮转后数组不变）
- // 1. 先整体翻转数组
- reverse(nums, 0, n - 1);
- // 2. 翻转前 k 个元素，使其恢复正确顺序
- reverse(nums, 0, k - 1);
- // 3. 翻转剩余的 n-k 个元素，使其恢复正确顺序
- reverse(nums, k, n - 1);
- }
- // 反转数组的辅助方法
- private void reverse(int[] nums, int i, int j) {
- while (i < j) { // 采用双指针法，交换 i 和 j 位置的元素
- int temp = nums[i];
- nums[i++] = nums[j]; // i 向右移动
- nums[j--] = temp; // j 向左移动
- }
- }
- }
使用 三次翻转 解决数组的右移问题：
- 团体翻转数组（第一次翻转）：把数组 [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:
- 输入: nums = [1,2,3,4,5,6,7], k = 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
- while (i < j) { // 采用双指针法，交换 i 和 j 位置的元素
- int temp = nums[i];
- nums[i++] = nums[j]; // i 向右移动
- nums[j--] = temp; // j 向左移动
- }
解答：
双指针法（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 轮转 等问题，如 字符串中的单词反转。
- 查抄是否为回文
- boolean isPalindrome(String s) {
- int i = 0, j = s.length() - 1;
- while (i < j) {
- if (s.charAt(i++) != s.charAt(j--)) return false;
- }
- return true;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
