1、题目描述
https://leetcode-cn.com/problems/contains-duplicate/
如果任意一值在数组中出现至少两次,函数返回 true
。如果数组中每个元素都不相同,则返回 false
。
输入: [1,2,3,1]
输出: true
输入: [1,2,3,4]
输出: false
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
2、代码详解
哈希:
用字典记录以及访问的元素
O(n),空间O(1)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
visited = set()
for num in nums:
if num in visited:
return True
visited.add(num)
return False
def containsDuplicate(nums):
return len(nums) != len(set(nums))
排序:O(nlogn),空间O(1)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if not nums: return False
nums.sort()
for i in range(1, len(nums)):
if nums[i - 1] == nums[i]: return True
return False
暴力:(超时)O(n*n),空间O(1)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
https://leetcode-cn.com/problems/contains-duplicate/solution/kong-jian-he-shi-jian-de-hu-huan-by-powcai/
本文地址:https://blog.csdn.net/IOT_victor/article/details/111127295