LeeCode - 189. Rotate Array(Array, Two Pointers, Math)*

문제

배열이 주어지면 배열을 오른쪽으로 k단계씩 회전합니다. 여기서 k는 음수가 아닙니다.

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

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

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]

풀이

자바입니다.
reverse

• k를 기준으로 3번 역순으로 정렬합니다.
  ex) nums={1,2,3,4,5,6,7}, k=3
  1.{4,3,2,1} 0 부터 nums.length-k-1 까지의 정렬입니다.
  2.{7,6,5} nums.length-1 부터 nums.length-k 까지의 정렬입니다.
  3.{4,3,2,1,7,6,5} 이렇게 정렬이 됩니다.
  최종적으로 0 부터 nums.length 까지 정렬하면
  {5,6,7,1,2,3,4} 이 됩니다.

class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length == 0 || k % nums.length == 0) return;

        int len = nums.length;
        k%=len; //nums.length>k 일 경우 방지위해
        reverse(nums, 0, len-k-1);
        reverse(nums, len-k, len-1);
        reverse(nums, 0, len-1);
        
    }
    public void reverse(int[] nums, int start, int end){
        // int tmp=0;
        while(start<end){
            int tmp = nums[start];
            nums[start]=nums[end];
            nums[end]=tmp;
            start++;
            end--;
        }
    }
}

다른풀이
https://leetcode.com/problems/rotate-array/discuss/54419/A-7-Line-Time-O(n)-In-Place-Solution-(No-Reversing)

• Sample [1,2,3,4,5,6,7,8,9] 3
  1) 1->4->7->1
  2) 2->5->8->2
  3) 3->6->9->3

class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length == 0 || k % nums.length == 0) return;
        int start = 0, i = start, curNum = nums[i], count = 0;
        while(count < nums.length){
            i = (i + k) % nums.length;
            int tmp = nums[i];
            nums[i] = curNum;
            if(i == start){
                start++;
                i = start;
                curNum = nums[i];
            }
            else curNum = tmp;
            
            count++;
        }
    }
}