Software Enginner πŸ‡―πŸ‡΅ and πŸ‡°πŸ‡·

Leetcode - Rotate Array

Problem Rotate Array
Difficulty Medium
Language Java
Time complexity $$O(n)$$
Space complexity $$O(1)$$

Problem,

Given an array, 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
  • -231 <= nums[i] <= 231 - 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?

Solution,

자, λ°°μ—΄ [1,2,3,4,5,6,7] λ₯Ό 잘 μ‚΄νŽ΄λ³΄μž. k=3 일 λ•Œ, κ²°κ³Όκ°€ [5,6,7,1,2,3,4] 라면, 1,2,3,4 와 5,6,7 을 λ”°λ‘œ 두고 생각할 수 μžˆμ„ 것이닀.

κ·Έλ ‡λ‹€λ©΄, κ·Ήκ°•μ˜ 꼼수λ₯Ό λΆ€λ €λ³Ό 수 μžˆλ‹€. μ™œλƒν•˜λ©΄, 잘 봐라. β€œRotate” 라고 ν•˜μ§€ μ•ŠλŠ”κ°€. 일단 뒀집고 μƒκ°ν•΄λ³΄μž.

[7,6,5,4,3,2,1] λ₯Ό 잘 보면 해닡이 보인닀. λ°”λ‘œ k=3 μ΄λΌλŠ” μ μ—μ„œ, μš°λ¦¬λŠ” 이 뒀집어진 배열을 두 번만 더 λ’€μ§‘μœΌλ©΄ λλ‚œλ‹€. μ–΄λ”œ 기점으둜? k=3 즉, k - 1 을 κΈ°μ€€μœΌλ‘œ.

그런데, λ†€λžκ²Œλ„ k λŠ” 10^5 κΉŒμ§€ μž…λ ₯을 받을 수 μžˆλ‹€. 즉, nums.length 보닀 더 클 수 μžˆλ‹€. 이러면 λ‹Ήμ—°νžˆ μ—λŸ¬κ°€ λ°œμƒν•œλ‹€. λ‚˜λ¨Έμ§€ 연산을 ν†΅ν•΄μ„œ N값보닀 클 λ•Œ μ–Έμ œλ‚˜ Nκ°’μœΌλ‘œ λ‚˜λˆˆ λ‚˜λ¨Έμ§€, 즉 μ‹€μ œ μš°λ¦¬κ°€ νšŒμ „μ‹œμΌœμ•Ό ν•˜λŠ” 수만 뽑아낼 수 μžˆλ‹€.

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length == 1 || k == nums.length) {
            return;
        }
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k % nums.length - 1);
        reverse(nums, k % nums.length, nums.length - 1);
    }
    
    private void reverse(int[] n, int l, int r) {
        while (l < r) {
            int tmp = n[l];
            n[l] = n[r];
            n[r] = tmp;
            ++l;
            --r;
        }
    }
}

참고둜 이 접근법은 μ—„μ²­λ‚œ λ…ΌμŸμ„ μ•ΌκΈ°μ‹œν‚¨ λ°©λ²•μ΄μ—ˆλ‹€.. 이 κΈ€ μ“°λ©΄μ„œ Solution 보고 μ•Œμ•˜λ‹€.