forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhaklee.py
More file actions
26 lines (20 loc) Β· 833 Bytes
/
haklee.py
File metadata and controls
26 lines (20 loc) Β· 833 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""TC: O(n), SC: O(n)
μμ΄λμ΄:
- [0, ..., n]μμ ν μ«μλ§ λΉ μ Έμλ μν©.
- [0, ..., n]μ setμΌλ‘ λ§λ λ€μ νΉμ μ«μκ° μ΄ setμ μλμ§ μ²΄ν¬νλ©΄ λλ€.
- κ·Έλ°λ° κ·Έλ κ² κ΅¬ννλ μ setμμ set(nums)λ₯Ό λΉΌκ³ λ¨μ μ«μλ₯Ό μ·¨νλ μ΅μ
μ κ²½μ°
κ°μ μ±λ₯μ΄ λμ¬ν
λ λ μ½λκ° μ§§μμ§λλ‘ νμμ λ°©μμΌλ‘ ꡬνν΄λ³΄μ.
SC:
- [0, ..., n]μΌλ‘ setμ λ§λλ λ°μ O(n).
- set(nums)μμ O(n).
- μ΄ O(n).
TC:
- [0, ..., n]μΌλ‘ setμ λ§λλ λ°μ O(n).
- set(nums)μμ O(n).
- setμ difference(μλ μ½λμμλ `-`)λ₯Ό νλ λ°μ O(n).
- setμ popμ νλ λ°μ O(1).
- μ΄ O(n).
"""
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return (set(range(len(nums) + 1)) - set(nums)).pop()