Repository navigation
LeetCode: 189 旋转数组三种解法 #86
Description
第一种
一次把所有数字右移，每次移动一个。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (k <= 0) {
return;
}
nums.insert(nums.begin(), nums[nums.size() - 1]);
nums.pop_back();
rotate(nums, k - 1);
}
};第二种
三次翻转，首先将前后两组数据先各自翻转一次，最后将整体所有数据翻转一次。
class Solution {
public:
void rotated(vector<int> &nums, int start, int end) {
int temp = 0;
while (start < end) {
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start ++;
end --;
}
return;
}
void rotate(vector<int>& nums, int k) {
if (nums.empty() || k == 0)
return;
if (k >= nums.size())
k %= nums.size();
if (k < nums.size())
k = k%nums.size();
rotated(nums, 0, nums.size() - k-1);
rotated(nums, nums.size() - k, nums.size()-1);
rotated(nums, 0, nums.size() - 1);
}
};第三种
从第一个数组依次向右移，记录被覆盖的数字，将覆盖的数字继续右移，知道最后所有数字都右移完成。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty() || k == 0)
return;
int length = nums.size();
int start = 0;
int i = 0;
int cur = nums[i];
int cnt = 0;
while (cnt++ < length) {
i = (i + k) % length;
int t = nums[i];
nums[i] = cur;
if (i == start) {
++start;
++i;
cur = nums[i];
} else {
cur = t;
}
}
}
};
Activity
[-]1[/-][+]LeetCode: 189 旋转数组三种解法[/+]