‘Find the Duplicate Number’ in LeetCode (Medium)
📌 Problem
https://leetcode.com/problems/find-the-duplicate-number/
📌 Answer
The point
- contains()
- Time complexity : O(n)
- Space complexity : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int findDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<Integer>();
for (int num : nums) {
if (seen.contains(num))
return num;
seen.add(num);
}
return -1;
}
}
📌 Other answer
The point
- Time complexity : O(n)
- Space complexity : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int findDuplicate(int[] nums) {
while (nums[0] != nums[nums[0]]) {
int nxt = nums[nums[0]];
nums[nums[0]] = nums[0];
nums[0] = nxt;
}
return nums[0];
}
}
The source : https://leetcode.com/problems/find-the-duplicate-number/solution/
📌 Words
- intuitive : 직관적인
Comments powered by Disqus.