The question is as follows:
Given an array, rotate the array to the right by k steps, where k is non-negative.
Here is my code:
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);
}
}
};
Test Case 1 :
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Here, My code compiled successfully and is giving the right solution.
Test Case 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Here, all the problem starts, my code giving the following error :
=================================================================
==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
I am what this error is, Please help.
The code crashed because that the it would be invalidated after calling push_back, to fix it we may directly call 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());
}
}
};
The algorithm in your code is not idental to right rotate, you are using left rotate. For right rotate, need to insert the last element into font, and then erase the last element, and we also need to modolus the vector's length to avoid uncessaray rotate, or there would be a waste, an accepted code might like:
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()));
}
}
};
And we can also call the STL algorithm: rotate, to rotate towards the right, we need to use the reverse iterator here:
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int r = k % nums.size();
std::rotate(nums.rbegin(), nums.rbegin() + r, nums.rend());
}
};
Your algorithm will cause the vector elements to be shifted at every insertion into the front, it is not efficient, think about we have a large vector, shift all the elements would be a bottle-neck.
The STL version might have some other performance enhancement since it may move the element range in batch rather than swap the elements one by one.
And we can also call std::reverse three times to implenment our own 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());
}
};
The last two versions are much faster than the previous ones, it's recommended to use them.