๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค.
๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python3์ ์ฌ์ฉํฉ๋๋ค.
๋์ด๋: Medium
ํค์๋: Array
๐ ๋ฌธ์
๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150
์ ์ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ง ๋ ์ฃผ์ด์ง ์์ด ์๋ ์ ์ k์ ๋ํด์ k ๋ฒ๋งํผ ๋ฐฐ์ด์ ์ค๋ฅธ์ชฝ์ผ๋ก ํ์ ์์ผ๋ผ
๐งช ์์
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]
๐ ๋ฌธ์ ํ์ด
์ถ๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ ๋ฐฉ๋ฒ. ๋ฐฐ์ด์ rotation์ (i + k) % len(nums) ๋ก indexingํ์ฌ ํด๊ฒฐํ ์ ์๋ค.
Runtime complexity : O(N)
Memory complexity : O(N)
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
N = len(nums)
tmp = [0] * N
for i in range(N):
tmp[(i+k) % N] = nums[i]
nums[:] = tmp
๐ก Follow up
- in-place๋ฅผ O(1) extra space์ผ๋ก ํด๊ฒฐํ ์ ์๋๊ฐ?
๋ฐ์ํ
'IN DEPTH CAKE > Supercoder' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ฝ๋ฉ/LeetCode150-(8)] Best Time to Buy and Sell Stock II (122) (0) | 2023.08.22 |
---|---|
[์ฝ๋ฉ/LeetCode150-(7)] Best Time to Buy and Sell Stock (121) (0) | 2023.08.20 |
[์ฝ๋ฉ/LeetCode150-(5)] Majority Element (169) (2) | 2023.08.18 |
[์ฝ๋ฉ/LeetCode150-(4)] Remove Duplicates from Sorted Array II(80) (2) | 2023.08.18 |
[์ฝ๋ฉ/LeetCode150-(3)] Remove Duplicates from Sorted Array (26) (2) | 2023.08.17 |