forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbhyun-kim.py
More file actions
29 lines (23 loc) · 676 Bytes
/
bhyun-kim.py
File metadata and controls
29 lines (23 loc) · 676 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
"""
268. Missing Number
https://leetcode.com/problems/missing-number/description/
Solution:
- Sort the input list
- For each index in the input list:
- If the index is not equal to the element:
- Return the index
- Return the length of the input list
Time complexity: O(nlogn+n)
- The sort function runs O(nlogn) times
- The for loop runs n times
Space complexity: O(1)
- No extra space is used
"""
from typing import List
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)):
if i != nums[i]:
return i
return len(nums)