旋转数组 LeetCode (189)

Question

问题如下：

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

这是我的代码：

 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：
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]

在这里，我的代码编译成功并给出了正确的解决方案。

测试用例 2：
输入：nums = [-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

我就是这个错误，请帮忙。

Answer 1

std::vector 的迭代器可能因 push_back() 而无效。

你应该直接使用nums.begin()而不保存擦除的迭代器。

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

Answer 2

代码崩溃是因为 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());
  }
};

后两个版本比前两个版本速度快很多，推荐使用。

旋转数组 LeetCode (189)

Rotate Array LeetCode (189)

c++

arrays

runtime-error