10
LeetCode 第 217 题：存在重复元素
source link: https://aywxbc.github.io/post/LeetCode%20%E7%AC%AC%20217%20%E9%A2%98%EF%BC%9A%E5%AD%98%E5%9C%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode
LeetCode 第 217 题：存在重复元素
DY发布于 十一月 21, 2021
1 mins.656
题目来源于 LeetCode 上第 217 题：存在重复元素。题目难度为 Easy，目前通过率为 55.6% 。
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
输入: [1,2,3,1]
输出: true输入: [1,2,3,4]
输出: false输入: [1,1,1,3,3,4,3,2,4,2]
输出: true方法一：排序法
思路：
- 倘若数组是有序的，则数组内的重复元素必会处于相邻的位置中。
- 因此，可以先对数组进行排序，得到一个有序数组后；再进行循环遍历，依次判断相邻的两个元素是否相等。若相等则说明存在重复的元素，反之，则不存在。
代码：
复杂度分析：
时间复杂度：O(nlogn)，其中 n 为数组的长度。需要对数组进行排序。
空间复杂度：O(logn)，其中 n 为数组的长度。注意我们在这里应当考虑
Arrays.sort(nums)递归调用栈的深度。
方法二：哈希表（Set）法
思路：
- 针对本题，可以考虑利用
Set不能存放重复元素的特性进行解决。 - 依次将数组内的元素插入到Set中，若插入时发现该元素已存在，则说明数组中存在重复元素；反之，则不存在。
代码：
复杂度分析：
- 时间复杂度：O(n)，其中 n 为数组的长度。
- 空间复杂度：O(n)，其中 n 为数组的长度。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK