189. 轮转数组（C++）

题目

给定一个整数数组 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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

题解

void rotate(std::vector<int>& nums, int k) {  
    int n = nums.size();  
    k = k % n; // 如果k大于n，取模以避免不必要的旋转  
  
    // 第一步：反转整个数组  
    std::reverse(nums.begin(), nums.end());  
  
    // 第二步：反转前k个元素  
    std::reverse(nums.begin(), nums.begin() + k);  
  
    // 第三步：反转剩下的元素  
    std::reverse(nums.begin() + k, nums.end());  
}  

算法原理

这个算法利用了数组反转（reversal）的性质来实现向右轮转。核心思想是将整个数组分为几个部分，并通过反转这些部分来达到轮转的效果，而不是逐个移动元素。

步骤分解

1. 计算有效的k值：
   由于k可能大于数组的长度n，直接按k进行轮转可能会导致不必要的操作。因此，我们首先计算k = k % n，确保k是小于n的非负整数。这样，我们就得到了一个“有效”的k值，它代表了实际需要轮转的步数。
2. 反转整个数组：
   接下来，我们反转整个数组。这一步的目的是将原本在数组末尾的元素移动到数组的开始位置，这是轮转操作的一部分。
3. 反转前k个元素：
   在第一步反转整个数组后，原本位于数组末尾的k个元素现在位于数组的开头。但是，这些元素可能并不是我们想要的顺序（即，它们可能不是原数组中连续的元素）。因此，我们需要将这k个元素再次反转，以恢复它们在原数组中的相对顺序（但位置已经移动到了开头）。
4. 反转剩余的元素：
   最后，除了前k个元素之外，数组中的其他元素也需要进行反转。这是因为，在第一步反转整个数组后，这些元素的顺序被打乱了。通过反转这些元素，我们可以恢复它们在原数组中的顺序（尽管它们现在位于数组的末尾部分）。

为什么这种方法有效？

这种方法之所以有效，是因为通过反转操作，我们实际上是在重新排列数组中的元素，而不是逐个移动它们。这种方法避免了逐个移动元素所带来的高昂时间成本（特别是对于大型数组）。

具体来说，通过三次反转操作，我们实际上是在做以下事情：

• 将数组末尾的元素“移动到”开头（第一次反转）。
• 将这些移动到开头的元素“排序”成它们在原数组中的顺序（第二次反转）。
• 将剩余的元素“排序”成它们在原数组中的顺序（第三次反转）。
• 最终，我们得到了一个向右轮转了k个位置的数组，而且这个过程是高效的，时间复杂度为O(n)。

原文地址：https://blog.csdn.net/weixin_45813121/article/details/142516888

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！