「力扣」第 217 题:存在重复元素(简单)

liweiwei1419 ... 2021-12-26 哈希表
  • 哈希表
About 3 min

# 题目描述

给定一个整数数组,判断是否存在重复元素。

如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false

示例 1:

输入: [1,2,3,1]
输出: true
1
2

示例 2:

输入: [1,2,3,4]
输出: false
1
2

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
1
2

Constraints:

  • 1nums.length1051 \le \text{nums.length} \le 10^5
  • 109nums[i]109-10^9 \le \text{nums[i]} \le 10^9

参考代码

class Solution:
    def containsDuplicate(self, nums):
        s = set()
        for num in nums:
            if num in s:
                return True
            else:
                s.add(num)
        return False
1
2
3
4
5
6
7
8
9

# 思路分析

这是一道非常简单的算法题,可以让刚接触算法题的朋友们热热身。解题思路也很容易想到:

  • 使用哈希表判重,以空间换时间;
  • 先将数组排序,如果有重复元素,它们就会相邻放置,遍历一遍数组,就容易发现相邻的重复元素。

两种方法各有优劣,体现在下面的「复杂度分析」中。

# 方法一:哈希表

参考代码

复杂度分析

  • 时间复杂度:O(N)O(N),这里 NN 是数组的长度,算法遍历了一次数组;
  • 空间复杂度:O(N)O(N),使用哈希表遍历了一遍数组中的每个元素。

# 方法二:对数组做预处理(排序)

排序以后再判断重复。

参考代码

复杂度分析

  • 时间复杂度:O(NlogN)O(N \log N),这里 NN 是数组的长度,算法先对数组排序,时间复杂度为 O(NlogN)O(N \log N),然后遍历了一次数组,时间复杂度为 O(N)O(N)
  • 空间复杂度:O(1)O(1),没有使用额外的存储空间,但是也修改了数组。
Last update: January 14, 2022 00:02
Contributors: liweiwei1419