일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- concurrency
- DWG
- Protocol
- Decorator
- 30. Substring with Concatenation of All Words
- shiba
- Regular Expression
- LeetCode
- 파이썬
- iterator
- Generator
- Convert Sorted List to Binary Search Tree
- 밴픽
- 715. Range Module
- 109. Convert Sorted List to Binary Search Tree
- 프로그래머스
- Python
- 컴퓨터의 구조
- data science
- t1
- Class
- kaggle
- 시바견
- 43. Multiply Strings
- Python Implementation
- Python Code
- attribute
- 315. Count of Smaller Numbers After Self
- Substring with Concatenation of All Words
- 운영체제
- Today
- Total
Scribbling
LeetCode: 287. Find the Duplicate Number 본문
LeetCode: 287. Find the Duplicate Number
focalpoint 2021. 12. 28. 20:35As a novice, it was not easy at all for me to solve this problem. I relied on other people's explanations and codes, and this post is to summarize their ideas.
It is very tricky to solve this problem within O(N) time & O(1) memory. (* without modifying the array)
The best way is "Floyd's Algorithm" as this problem can be seen as a linked list with a cycle.
Check out the below video for further explanations.
https://www.youtube.com/watch?v=wjYnzkAhcNk&t=876s
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
slow, fast = nums[0], nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
p1, p2 = 0, slow
while p1 != p2:
p1 = nums[p1]
p2 = nums[p2]
return p1
Another solution is using binary search.
This algorithm's time complexity is O(NlogN), but this solution is more thinkable in my opinion. (As it is almost impossible to come up with Floyd's algorithm when facing this problem for the first time except for the most brilliant guys).
If the code below is not intuitive or easy to understand, the link below will be helpful.
Two Solutions (with explanation): O(nlog(n)) and O(n) time , O(1) space, without changing the input array - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
if cnt <= mid:
low = mid + 1
else:
high = mid
return low
'Computer Science > Coding Test' 카테고리의 다른 글
LeetCode: 328. Odd Even Linked List (0) | 2021.12.31 |
---|---|
LeetCode: 289. Game of Life (0) | 2021.12.29 |
LeetCode: 279. Perfect Squares (0) | 2021.12.27 |
LeetCode: 240. Search a 2D Matrix II (0) | 2021.12.27 |
LeetCode: 283. Move Zeroes (0) | 2021.12.25 |