本文主要是介绍LeetCode 算法：轮转数组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
进阶： - 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
题解
原地轮转数组
- 题解：
这种方法通过三次反转来实现原地轮转，不需要额外的空间。
步骤：
- 反转整个数组。
- 反转前 k 个元素。
- 反转 k 个元素后的剩余部分。
- 复杂度：时间复杂度O(n)，空间复杂度 O(n)。
- 过程：
头文件和命名空间:
#include <vector>: 包含标准库中的vector容器。#include <iostream>: 包含输入输出流。using namespace std;: 使用标准命名空间，这样我们就不需要在标准库类型和函数前加std::前缀。辅助函数
reverse:
- 函数原型：
void reverse(vector<int>& nums, int start, int end)。- 功能：反转
nums数组中从索引start到索引end的部分。- 实现：使用
while循环和swap函数来交换start和end指向的元素，然后start向前移动，end向后移动，直到start大于或等于end。
Solution类:
- 包含一个公有成员函数
rotate，用于实现数组的轮转。- 输入参数：
nums是要轮转的数组，k是轮转的步数。- 实现逻辑：
- 首先检查
nums是否为空或者k是否是数组长度的倍数，如果是，则直接返回，因为不需要做任何操作。- 然后，通过三次反转实现数组的轮转：
- 反转整个数组。
- 反转数组的前
k个元素。- 反转数组从索引
k到末尾的部分。主函数
main:
- 创建
Solution类的实例。- 定义一个
vector<int>类型的数组nums，初始化为{1, 2, 3, 4, 5, 6, 7}。- 定义一个整数
k，值为3，表示要将数组向右轮转3步。- 打印原始数组。
- 调用
rotate方法对数组进行轮转。- 打印轮转后的数组。
输出:
- 程序首先打印原始数组。
- 然后调用
rotate方法，将数组[1, 2, 3, 4, 5, 6, 7]向右轮转3步，结果应该是[5, 6, 7, 1, 2, 3, 4]。- 最后打印轮转后的数组。
- c++ demo：
#include <vector>
#include <iostream>using namespace std;// 辅助函数，用于反转数组中从 start 到 end 的部分
void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start++;end--;}
}// 轮转数组的主要函数
class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();if (n == 0 || k % n == 0) return; // 如果数组为空或k是数组长度的倍数，不需要旋转// 反转整个数组reverse(nums, 0, n - 1);// 反转前 k 个元素reverse(nums, 0, k - 1);// 反转剩余的 n - k 个元素reverse(nums, k, n - 1);}
};// 主函数，用于演示
int main() {Solution solution;vector<int> nums = {1, 2, 3, 4, 5, 6, 7};int k = 3;cout << "Original array: ";for (int num : nums) {cout << num << " ";}cout << endl;solution.rotate(nums, k);cout << "Rotated array: ";for (int num : nums) {cout << num << " ";}cout << endl;return 0;
}
- 输出结果：
Original array: {1, 2, 3, 4, 5, 6, 7}
Rotated array: {5, 6, 7, 1, 2, 3, 4}
其他题解
1. 额外空间法
这种方法使用额外的数组来存储元素，然后复制回原数组。这种方法简单，但不是原地操作。
void rotate(vector<int>& nums, int k) {vector<int> temp(nums.size());for (int i = 0; i < nums.size(); ++i) {temp[(i + k) % nums.size()] = nums[i];}nums = temp;
}
2. 反转法（原地操作）
这种方法通过三次反转来实现原地轮转，不需要额外的空间。
步骤：
- 反转整个数组。
- 反转前
k个元素。 - 反转
k个元素后的剩余部分。
void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n; // 避免 k 大于数组长度reverse(nums, 0, n - 1); // 反转整个数组reverse(nums, 0, k - 1); // 反转前 k 个元素reverse(nums, k, n - 1); // 反转剩余元素
}void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start++;end--;}
}
3. 循环交换法
这种方法通过循环交换元素来实现轮转，但可能需要多次循环。
void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n;for (int i = 0; i < k; ++i) {swap(nums[i], nums[n - 1 - i]);}
}
4. 递归法
这种方法通过递归地将问题分解为更小的问题来解决。
void rotate(vector<int>& nums, int k) {k %= nums.size();if (k == 0) return;rotate(nums, k - 1);swap(nums[0], nums[nums.size() - k]);
}
5. 滑动窗口法
这种方法使用一个滑动窗口来逐步移动元素。
void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n;for (int i = 0; i < k; ++i) {nums.push_back(nums[i]);}for (int i = 0; i < n; ++i) {nums[i] = nums[i + k];}nums.erase(nums.begin(), nums.begin() + k);
}
每种方法都有其优缺点，选择哪种方法取决于具体问题的要求和个人偏好。原地操作通常更优，因为它不需要额外的存储空间。
这篇关于LeetCode 算法：轮转数组c++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
