189. Rotate Array
189. Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1 0 <= k <= 10^5
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
문제 해석
- 맨 뒤에서부터 k개의 인덱스를 앞으로 옮겨 정렬하는 문제이다.
- 이 문제에서 중요한 것은 Follow up 이다.
- 풀이방법 3가지이상 + 추가공간 생성없이 (O(1)) 공간복잡도로 최적의 해결을 찾아 공부하는 것이 중요한 문제이다.
구현(1)
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
vector<int> rotated(n);
for(int i = 0; i < n; i++)
{
rotated[(i + k) % n] = nums[i];
}
for(int i = 0; i< n; i++)
{
nums[i] = rotated[i];
}
}
};
코드 해석
- **위 코드는 새로운 공간 vector
rotated(n)를 생성하기 때문에 공간 복잡도는 \(O(n\)) 으로 최적의 알고리즘은 아니다**
k = k % n;
- 이 문제를 해결하는 핵심 아이디어
- k 가 nums.size() 보다 큰 경우를 생각해야하는 문제였다.
- 만약 k 가 nums.size()보다 크다면 딱 크기만큼 회전하면 원래의 nums와 같아지므로 결국 나머지만 정렬하면 동일한 결과 를 얻을 수 있다는 것이다.
구현(2)
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reversed(nums, 0, n-1);
reversed(nums, 0, k-1);
reversed(nums, k, n-1);
}
void reversed(vector<int>& nums, int left, int right) {
while(left < right)
{
swap(nums[left], nums[right]);
left++;
right--;
}
}
};
코드 해석
- 새로운 공간을 할당하지 않고 원본에서 해결하는 코드이다.
- 즉, 시간 복잡도 (O(n)), 공간 복잡도(O(1)) 이다.
void reversed(vector<int>& nums, int left, int right) {
while(left < right)
{
swap(nums[left], nums[right]);
left++;
right--;
}
}
- Two Pointer 방식의 풀이이다.(이제 투 포인터는 많이 풀어서 문제를 보면 투 포인터로 풀어야할 것 같다는 감은 온다.)
- swap() STL은 시간 복잡도 (O(n)), 공간 복잡도(O(1)) 를 가진다.