LeetCode 189 Rotate Array(旋转数组)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50600861 翻译通过K步将一个有着n个元素的数组旋转到右侧。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50600861

翻译

通过K步将一个有着n个元素的数组旋转到右侧。

例如,
给定n = 7和k = 3,数组[1,2,3,4,5,6,7]会被旋转成[5,6,7,1,2,3,4]。

批注:
尽你可能尝试多种解决方案,这里至少存在3种不同的方式去解决这个问题。

原文

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

分析

第一种方法

我所想到的第一种方式是另设置一个vector,然后逐个元素添加进去,最后将这个vector赋值给nums。添加方式为将右边的k个元素添加进去,再将左边的n-k个元素添加进去。

具体代码为:

void rotate(vector<int> &nums, int k) {
    if (nums.size() == 1) return;
    if (k > nums.size())  k %= nums.size();
    vector<int> newNums;
    for (int i = nums.size() - k; i < nums.size(); ++i)
        newNums.push_back(nums[i]);
    for (int i = 0; i < nums.size() - k; ++i)
        newNums.push_back(nums[i]);
    nums = newNums;
}

Runtime: 28 ms

超时方法

还有一个最简单的方法,不过妥妥的超时了……

void rotate(vector<int> &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    while (k > 0) {
        int temp = nums[nums.size() - 1];
        for (int i = nums.size() -1; i >0; --i) {
            nums[i] = nums[i - 1];
        }
        nums[0] = temp;
        k--;
    }
}

Time Limit Exceeded

第二种方法

上面那种方法不行,继续改进第一种方法。同样是将vector切成左右两边。

void rotate(vector<int> &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    vector<int> extra(nums.begin(), nums.begin() + nums.size() - k);
    nums.erase(nums.begin(), nums.begin() + nums.size() - k);
    nums.insert(nums.end(), extra.begin(), extra.end());
}

Runtime: 28 ms

第二种方法改进

试试颠倒顺序呢?

void rotate(vector<int> &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    vector<int> extra(nums.end() - k, nums.end());
    nums.erase(nums.end() - k, nums.end());
    nums.insert(nums.begin(), extra.begin(), extra.end());
}

Runtime: 24 ms

要少了4秒呢。

第三种方法

还有一种方法,可以使用STL自带的rotate()函数……

void rotate(vector<int>& nums, int k) {
    int len = nums.size();
    if (len > 1) {
        k %= len;
        std::rotate(nums.begin(), nums.end() - k, nums.end());
    }
}
目录
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
17天前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
19天前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
|
26天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
18 4
|
26天前
|
机器学习/深度学习
Leetcode第48题(旋转图像)
这篇文章介绍了LeetCode第48题“旋转图像”的解题方法,通过原地修改二维矩阵实现图像的顺时针旋转90度。
25 0
Leetcode第48题(旋转图像)
|
26天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
16 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
存储 JavaScript 前端开发
JavaScript Array(数组) 对象
JavaScript Array(数组) 对象
24 3
|
26天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
50 0
|
26天前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
15 0