217. Contains Duplicate
题目:
https://leetcode.com/problems/contains-duplicate/
难度:
Easy
我直接sort，然后比较相邻的元素，这样O(n)，也是笨办法，居然unlocked a solution，所以来读读解答.
三个办法：
- linear search O(n^2)
- sort O(n)
- hashtable
我用的sort
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return True
return False
看给的Java解法
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>(nums.length);
for (int x: nums) {
if (set.contains(x)) return true;
set.add(x);
}
return false;
}
还有一个取巧的Python解法，我也看到了
class Solution(object):
def containsDuplicate(self, nums):
if len(nums) > len(set(nums)):
return True
return False
