力扣数据结构入门专栏分析 ①
一、题目描述：
题目链接：217. 存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]输出：true示例 2：
输入：nums = [1,2,3,4]输出：false示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]输出：true
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109
题目来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/contains-duplicate著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
- 看到这道题，我的第一想法是再建立一个数组arr，遍历整数数组 nums，然后每次将获取的元素与arr中值进行比较，如果没有就放入arr中，如果有就返回false。遍历nums完就返回true。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
- 用上面的思路结果超时了....后来发现我们可以先排序，然后比较相邻的两个元素是否相等。还可以使用Java的HashSet的不可添加重复元素特性来完成这道算法题。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
- 解法一：排序
- 时间复杂度：O(NlogN)
- 空间复杂度：O(logN)
- 解法二：Java使用HashSet
- 时间复杂度：O(N)O(N)
- 空间复杂度：O(N)O(N)
三、AC 代码：
C：
intcmpfunc (constvoid*a, constvoid*b)
{
return ( *(int*)a-*(int*)b );
}
boolcontainsDuplicate(int*nums, intnumsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
for (inti=0; i<numsSize-1; i++) {
if (nums[i] ==nums[i+1]) {
returntrue;
}
}
returnfalse;
}
Java：
classSolution {
publicbooleancontainsDuplicate(int[] nums) {
Arrays.sort(nums);
for (inti=0; i<nums.length-1; i++) {
if (nums[i] ==nums[i+1]) {
returntrue;
}
}
returnfalse;
}
}
Java：
classSolution {
publicbooleancontainsDuplicate(int[] nums) {
Set<Integer>set=newHashSet<Integer>();
for (intx : nums) {
if (!set.add(x)) {
returntrue;
}
}
returnfalse;
}
}
四、总结：
这不是什么难题，但是当实际问题中遇到数据的量比较大时，我那种暴力算法就会超时，稍微改进一下可以将数组进行排序，然后比较相邻的的数是否有重复的，也没必要比较两边的，只需要比较后面那个即可。HashSet也是个好东西，有机会学一下。这个HashSet的add方法其实底层就是调用HashMap的put方法，不过与HashMap的put有些不同，put时如果key重复了，会覆盖原来的值，不然就返回null。而这里使用这个HashSet的add方法，如果添加时key没有重复，就返回true，否则返回false。
