34人参与 • 2025-04-12 • C/C++
给定一个长度为 n
的整数数组 nums
,请将数组中的元素向右轮转 k
个位置,其中 k
是非负数。
示例:
输入: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]
要求:
提示:
k
大于数组长度 n
的情况。数组轮转的本质是将数组中的元素整体向右移动 k
个位置,超出数组边界的元素会“循环”回到数组的开头。
关键点:
k
大于等于数组长度 n
时,实际轮转的步数是 k % n
。 例如,如果 n = 7
,k = 9
,那么实际轮转 2 步。 因此,需要对 k
进行取模运算。思路 1: 暴力法(重复移动)。
k
次。思路 2: 使用额外数组。
new_nums
,长度与原数组相同。nums
中的每个元素 nums[i]
放到新数组的 new_nums[(i + k) % n]
位置上。new_nums
复制回原数组 nums
。思路 3: 反转数组。
k % n
个元素反转。n - (k % n)
个元素反转。nums = [1, 2, 3, 4, 5, 6, 7], k = 3
[7, 6, 5, 4, 3, 2, 1]
[5, 6, 7, 4, 3, 2, 1]
[5, 6, 7, 1, 2, 3, 4]
思路 4: 循环替换。
(0 + k) % n
位置,再将该位置的元素移动到 (0 + 2k) % n
位置,以此类推。思路 5: 使用gcd(最大公约数)来优化循环替换。
如果 n
和 k
的最大公约数是 1,那么只需要一个循环就能完成所有的替换。 但如果最大公约数不是1,则需要多个循环。
找到 n
和 k
的最大公约数 gcd
。 循环从 0
到 gcd - 1
。 在每个循环中,执行循环替换。
优点: 优化了循环替换算法
缺点: 需要计算最大公约数,复杂度增加。
复杂度分析:
解决方案 | 时间复杂度 | 空间复杂度 | 原地算法? |
---|---|---|---|
暴力法 | o(n * k) | o(1) | 是 |
额外数组 | o(n) | o(n) | 否 |
反转数组 | o(n) | o(1) | 是 |
循环替换 | o(n) | o(1) | 是 |
gcd循环替换 | o(n) | o(1) | 是 |
new_nums
,长度与原数组相同。nums
中的后 k % num.size()
个元素 nums[i]
放到新数组的开头位置上,其他元素依次放在末尾。new_nums
复制回原数组 nums
。class solution { public: void rotate(vector<int>& nums, int k) { unsigned n = k % nums.size(); if (n == 0) return; vector<int> ret(nums.end() - n, nums.end()); for (unsigned i = 0; i < (nums.size() - n); ++i) ret.emplace_back(nums[i]); std::swap(ret, nums); } };
时间复杂度:
这种方法实现相对容易,而且容易理解。
k % n
个元素反转。n - (k % n)
个元素反转。原理:
nums = [1, 2, 3, 4, 5, 6, 7], k = 3
[7, 6, 5, 4, 3, 2, 1]
[5, 6, 7, 4, 3, 2, 1]
[5, 6, 7, 1, 2, 3, 4]
代码实现:
class solution { public: void rotate(vector<int>& nums, int k) { unsigned n = k % nums.size(); if (n == 0) return; unsigned size = nums.size(); for (unsigned i = 0; i < size / 2; ++i) std::swap(nums[i], nums[size - i - 1]); for (unsigned i = 0; i < n / 2; ++i) std::swap(nums[i], nums[n - i -1]); for (unsigned i = 0; i < (size - n) / 2; ++i) std::swap(nums[i + n], nums[size - i - 1]); } };
从位置 0 开始,将该位置的元素移动到 (0 + k) % n
位置,再将该位置的元素移动到 (0 + 2k) % n
位置,以此类推。
为了避免重复循环,需要记录已经访问过的位置,或者使用一个计数器来控制循环的次数。
可以使用gcd(最大公约数)来优化循环替换:
如果 n
和 k
的最大公约数是 1,那么只需要一个循环就能完成所有的替换。 但如果最大公约数不是1,则需要多个循环。
找到 n
和 k
的最大公约数 gcd
。 循环从 0
到 gcd - 1
。 在每个循环中,执行循环替换。
class solution { public: void rotate(vector<int>& nums, int k) { unsigned n = nums.size(); int gcd = std::gcd(n, k % n); for (int i = 0; i < gcd; ++i) { int cur = i; int pre = nums[cur]; do { int next = (cur + k) % n; std::swap(nums[next], pre); cur = next; } while (cur != i); } } };
c++中数组轮转问题的五种解决方案:暴力法、额外数组、反转数组、循环替换以及gcd优化循环替换。分析了每种算法的时间和空间复杂度,并特别关注了原地算法的实现。通过对比不同方案,展示了如何在时间和空间之间权衡,最终实现高效且节省空间的数组轮转。
其中,反转数组和gcd优化循环替换是在实际项目中推荐使用的。
以上就是在c++中实现高效的数组原地轮转的方法总结的详细内容,更多关于c++数组原地轮转的资料请关注代码网其它相关文章!
您想发表意见!!点此发布评论
版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。
发表评论