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 λ³΄κ³ μμλ€.