[leetcode 189] Rotate Array

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

Follow up:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

 

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 <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

문제 풀이:

포인트: 공간복잡도를 o(1)로 하기!

처음엔 bruteforce로 한개씩 k번 돌렸더니 TLE가 떴다...ㅠㅠ

 

그래서 본 솔루션: 1. k씩 직접 옮긴다. 2. reverse사용

 

1. k씩 직접 옮기기.

리트코드 솔루션 참고

count는 정렬된 배열요소의 수를 체크한다. 

그외에는 하나씩 옮기는 것과 동일하다. 단지 k단계씩 옮길뿐.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len;
        
        int count = 0;
        for(int start = 0; count<len; start++){
            int cur = start;
            int curVal = nums[cur];
            
            do{
                int next = (cur+k)%len;
                int nextVal = nums[next];
                nums[next] = curVal;
                curVal = nextVal;
                cur = next;
                count++;
            }while(cur != start);
        }
        
    }
};

 

2. reverse사용

정말 신기하게도 세 번의 reverse로도 움직임을 구현할 수 있다.

arr={1,2,3,4,5,6,7}, k=2라고 해보자

먼저 전체 reverse를 진행한다. 7 6 5 4 3 2 1 이 될 것이다.

 

여기서 [0,1] [2,6]을 쪼개서 각각 reverse한다면

6 7 1 2 3 4 5가 된다!

 

배열 문제에서 은근 reverse를 많이 사용하게 되는 것 같다.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len;
        
       //reverse 사용
        reverse(nums.begin(), nums.end());
        
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
        
    }
};