文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++怎么实现旋转数组

2023-06-20 16:24

关注

本篇内容主要讲解“C++怎么实现旋转数组”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++怎么实现旋转数组”吧!

Rotate Array 旋转数组

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7]

and k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right:

[7,1,2,3,4,5,6]

rotate 2 steps to the right:

[6,7,1,2,3,4,5]

rotate 3 steps to the right:

[5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99]

and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

新题抢先刷,这道题标为 Easy,应该不是很难,我们先来看一种 O(n) 的空间复杂度的方法,我们复制一个和 nums 一样的数组,然后利用映射关系 i -> (i+k)%n 来交换数字。代码如下:

解法一:

class Solution {public:    void rotate(vector<int>& nums, int k) {        vector<int> t = nums;        for (int i = 0; i < nums.size(); ++i) {            nums[(i + k) % nums.size()] = t[i];        }    }};

由于提示中要求我们空间复杂度为 O(1),所以我们不能用辅助数组,上面的思想还是可以使用的,但是写法就复杂的多,而且需要用到很多的辅助变量,我们还是要将 nums[idx] 上的数字移动到 nums[(idx+k) % n] 上去,为了防止数据覆盖丢失,我们需要用额外的变量来保存,这里用了 pre 和 cur,其中 cur 初始化为了数组的第一个数字,然后当然需要变量 idx 标明当前在交换的位置,还需要一个变量 start,这个是为了防止陷入死循环的,初始化为0,一旦当 idx 变到了 strat 的位置,则 start 自增1,再赋值给 idx,这样 idx 的位置也改变了,可以继续进行交换了。举个例子,假如 [1, 2, 3, 4], K=2 的话,那么 idx=0,下一次变为 idx = (idx+k) % n = 2,再下一次又变成了 idx = (idx+k) % n = 0,此时明显 1 和 3 的位置还没有处理过,所以当我们发现 idx 和 start 相等,则二者均自增1,那么此时 idx=1,下一次变为 idx = (idx+k) % n = 3,就可以交换完所有的数字了。

因为长度为n的数组只需要更新n次,所以我们用一个 for 循环来处理n次。首先 pre 更新为 cur,然后计算新的 idx 的位置,然后将 nums[idx] 上的值先存到 cur 上,然后把 pre 赋值给 nums[idx],这相当于把上一轮的 nums[idx] 赋给了新的一轮,完成了数字的交换,然后 if 语句判断是否会变到处理过的数字,参见上面一段的解释,我们用题目中的例子1来展示下面这种算法的 nums 的变化过程:

1 2 3 4 5 6 7
1 2 3 1 5 6 7
1 2 3 1 5 6 4
1 2 7 1 5 6 4
1 2 7 1 5 3 4
1 6 7 1 5 3 4
1 6 7 1 2 3 4
5 6 7 1 2 3 4

解法二:

class Solution {public:    void rotate(vector<int>& nums, int k) {        if (nums.empty() || (k %= nums.size()) == 0) return;        int start = 0, idx = 0, pre = 0, cur = nums[0], n = nums.size();        for (int i = 0; i < n; ++i) {            pre = cur;            idx = (idx + k) % n;            cur = nums[idx];            nums[idx] = pre;            if (idx == start) {                idx = ++start;                cur = nums[idx];            }        }    }};

这道题其实还有种类似翻转字符的方法,思路是先把前 n-k 个数字翻转一下,再把后k个数字翻转一下,最后再把整个数组翻转一下:

1 2 3 4 5 6 7
4 3 2 1 5 6 7
4 3 2 1 7 6 5
5 6 7 1 2 3 4

解法三:

class Solution {public:    void rotate(vector<int>& nums, int k) {        if (nums.empty() || (k %= nums.size()) == 0) return;        int n = nums.size();        reverse(nums.begin(), nums.begin() + n - k);        reverse(nums.begin() + n - k, nums.end());        reverse(nums.begin(), nums.end());    }};

由于旋转数组的操作也可以看做从数组的末尾取k个数组放入数组的开头,所以我们用 STL 的 push_back 和 erase 可以很容易的实现这些操作。

解法四:

class Solution {public:    void rotate(vector<int>& nums, int k) {        if (nums.empty() || (k %= nums.size()) == 0) return;        int n = nums.size();        for (int i = 0; i < n - k; ++i) {            nums.push_back(nums[0]);            nums.erase(nums.begin());        }    }};

下面这种方法其实还蛮独特的,通过不停的交换某两个数字的位置来实现旋转,根据网上这个帖子的思路改写而来,数组改变过程如下:

1 2 3 4 5 6 7
5 2 3 4 1 6 7
5 6 3 4 1 2 7
5 6 7 4 1 2 3
5 6 7 1 4 2 3
5 6 7 1 2 4 3
5 6 7 1 2 3 4

解法五:

class Solution {public:    void rotate(vector<int>& nums, int k) {        if (nums.empty()) return;        int n = nums.size(), start = 0;           while (n && (k %= n)) {            for (int i = 0; i < k; ++i) {                swap(nums[i + start], nums[n - k + i + start]);            }            n -= k;            start += k;        }    }};

到此,相信大家对“C++怎么实现旋转数组”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯