forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshinsj4653.py
More file actions
49 lines (33 loc) ยท 785 Bytes
/
shinsj4653.py
File metadata and controls
49 lines (33 loc) ยท 785 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
[๋ฌธ์ ํ์ด]
# Inputs
nums -> n๊ฐ์ ์ค๋ณต๋์ง ์๋ ์ซ์๋ค (0 ~ n)
# Outputs
์ ์ผํ๊ฒ 0 ~ n ๋ฒ์์ ํฌํจ๋์ด ์์ง ์์ ์
# Constraints
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.
# Ideas
O(1) SC, O(n) TC๋ก ํ ์ ์์๊น?
-> ์ฒ์์ ๋น์ฐํ ์ฌ์ ์ฐ๋ฉด ๋๊ฒ ์งํ์ง๋ง, O(1) SC๊ฐ ์๋จ
์ ๋ ฌ๋ nlogn..
๊ธธ์ด : n
0๋ถํฐ n ๊น์ง ํฉ =>
n = 3
0 1 2 3 -> 6
sum(nums) -> 4
๋จ์ ์ : 2
[ํ๊ณ ]
์ด๊ฒ ๋ง๋ค
1๋ถํฐ n ๊น์ง ํฉ ๊ณต์ -> (n * (n + 1)) // 2
"""
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
s = sum(nums)
total_s = 0
for i in range(n + 1):
total_s += i
return total_s - s