旋转数组LeetCode(189)

本文介绍了旋转数组LeetCode(189)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

问题如下：

给定一个数组，将该数组向右旋转k步，其中k为非负数。

以下是我的代码：

class Solution { public: void rotate(vector<int>& nums, int k) { int r =nums.size()-k; vector<int>::iterator it; it = nums.begin(); for(int i=0;i<r;i++){ nums.push_back(nums[0]); nums.erase(it); } } };

测试用例1： 输入：数字=[1，2，3，4，5，6，7]，k=3 输出：[5，6，7，1，2，3，4]

在这里，我的代码已成功编译，并且提供了正确的解决方案。

测试用例2： 输入：数字=[-1，-100，3，99]，k=2 输出：[3，99，-1，-100]

在这里，所有问题都开始了，我的代码显示以下错误：

================================================================= ==32==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000094 at pc 0x0000003189cf bp 0x7ffe0e44adf0 sp 0x7ffe0e44a5b8 READ of size 68719476672 at 0x602000000094 thread T0 #5 0x7f15fa2470b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 0x6020000000a0 is located 0 bytes to the right of 16-byte region [0x602000000090,0x6020000000a0) freed by thread T0 here: #4 0x7f15fa2470b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) previously allocated by thread T0 here: #6 0x7f15fa2470b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) Shadow bytes around the buggy address: 0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa =>0x0c047fff8010: fa fa[fd]fd fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==32==ABORTING

我就是此错误，请帮助。

推荐答案

代码崩溃，因为it调用push_back后会invalidated，可以直接调用begin修复。

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

代码中的算法与右旋转无关，您使用的是左旋转。对于右旋转，需要将最后一个元素插入字体，然后擦除最后一个元素，我们还需要对向量的长度进行模型化，以避免不连续的旋转，否则会有浪费，公认的代码可能如下所示：

class Solution { public: void rotate(vector<int>& nums, int k) { int r = k % nums.size(); for (int i = 0; i < r; i++) { nums.insert(nums.begin(), nums.back()); nums.erase(std::prev(nums.end())); } } };

我们还可以调用STL算法：rotate，要向右旋转，我们需要在这里使用反向迭代器：

class Solution { public: void rotate(vector<int>& nums, int k) { int r = k % nums.size(); std::rotate(nums.rbegin(), nums.rbegin() + r, nums.rend()); } };

您的算法会导致向量元素在每次插入到前面时都会移位，效率不高，想想我们有一个很大的向量，移位所有元素都会成为瓶颈。

STL版本可能有一些其他性能增强，因为它可以成批移动元素范围，而不是逐个交换元素。

我们也可以调用三次std::reverse来实现我们自己的rotate：

class Solution { public: void rotate(vector<int>& nums, int k) { int r = k % nums.size(); std::reverse(nums.begin(), nums.end()); std::reverse(nums.begin(), nums.begin() + r); std::reverse(nums.begin() + r, nums.end()); } };

最后两个版本比前两个版本快很多，建议使用。