it编程 > 编程语言 > C/C++

在C++中实现高效的数组原地轮转的方法总结

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 个位置,超出数组边界的元素会“循环”回到数组的开头。

关键点:

思路 1: 暴力法(重复移动)。

思路 2: 使用额外数组。

思路 3: 反转数组。

思路 4: 循环替换。

思路 5: 使用gcd(最大公约数)来优化循环替换。

复杂度分析:

解决方案时间复杂度空间复杂度原地算法?
暴力法o(n * k)o(1)
额外数组o(n)o(n)
反转数组o(n)o(1)
循环替换o(n)o(1)
gcd循环替换o(n)o(1)

三、算法实现

3.1、使用额外数组(效果较差)

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);
    }
};

时间复杂度:

3.2、反转数组3次(实现简单)

这种方法实现相对容易,而且容易理解。

原理:

代码实现:

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]);
    }
};

3.3、循环替换(较为复杂)

从位置 0 开始,将该位置的元素移动到 (0 + k) % n 位置,再将该位置的元素移动到 (0 + 2k) % n 位置,以此类推。

为了避免重复循环,需要记录已经访问过的位置,或者使用一个计数器来控制循环的次数。

可以使用gcd(最大公约数)来优化循环替换:

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++数组原地轮转的资料请关注代码网其它相关文章!

(0)
打赏 微信扫一扫 微信扫一扫

您想发表意见!!点此发布评论

推荐阅读

如何高效移除C++关联容器中的元素

04-12

C++ vector的常见用法超详细讲解

04-12

Qt spdlog日志模块的使用详解

04-12

dev c++ 怎么添加外部库

04-08

c++ 函数重载的规则是什么

04-08

c/c++中的左值右值详解

04-08

猜你喜欢

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论