189. Rotate Array

Description:

https://leetcode.com/problems/rotate-array/#/description

Algorithm:

Solution1: shift for k times

Solution2: use new vector. Initialize the new vector and reEvaluate the elements. The new offset = k % n; The new index = (i + n – offset) % n;

Solution3: use new vector. Push_back the new element one buy one. The new offset = n – k % n; The new index = (i + offset) % n;

Code:



#ifdef Solution1
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int offset = k % n;
int tmp;
if (offset < n / 2)
for (int j = 0; j < offset; j++)
{
tmp = nums[n - 1];
for (int i = 0; i < nums.size();i++)
{
swap(nums[i], tmp);
}
}
else
for (int j = 0; j < n - offset; j++)
{
tmp = nums[0];
for (int i = nums.size() - 1; i >= 0;i--)
{
swap(nums[i], tmp);
}
}
}
};
#endif
#ifdef Solution2
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> result = vector<int>(n, 0);
int offset = k % n;
for (int i = 0; i < nums.size();i++)
{
result[i] = nums[(i + n - offset) % n];
}nums = result;
}
};
#endif
#ifdef Solution3
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int offset = n - k % n;
vector<int> result;
for (int i = 0; i < nums.size();i++)
result.push_back(nums[(i + offset) % n]);
nums = result;
}
};
#endif

 

Timing & Space:

• Solution1:
  • Time: Worst: O(n * n/2), Best O(n), Avg O(n * n/4)
  • Space: O(1)
• Solution2:
  • Time: O(n)
  • Space: O(n)
• Solution3:
  • Time: O(n)
  • Space: O(n)