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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
"""
Question
Duplicate Integer
Easy
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
Example 1:
Input: nums = [1, 2, 3, 3]
Output: true
Example 2:
Input: nums = [1, 2, 3, 4]
Output: false
"""
from typing import List
class Solution:
# 1. brute force
def brute_force(self, nums: List[int]) -> bool:
return False
# 2. sorting
def sorting(self, nums: List[int]) -> bool:
return False
# 3. hashset
def hashset(self, nums: List[int]) -> bool:
hs = set()
for i in range(len(nums)):
if nums[i] in hs:
return True
hs.add(nums[i])
return False
case1 = [1, 2, 3, 4, 5]
case2 = [2, 2, 3, 4, 5]
case3 = [3, 4, 1, 6, 3]
solution = Solution()
print(f"hashset case1: {solution.hashset(case1)}")
print(f"hashset case2: {solution.hashset(case2)}")
print(f"hashset case3: {solution.hashset(case3)}")
"""
Solution
url: https://neetcode.io/problems/duplicate-integer
video: https://youtu.be/3OamzN90kPg
1. brute force
time: O(n^2)
space: O(1)
2. sort
time: O(nlogn)
space: O(1)
3. hashset
time: O(n)
space: O(n)
code:
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
hashset = set()
for n in nums:
if n in hashset:
return True
hashset.add(n)
return False
"""
|
