LeetCode217（存在重复元素）

发表于 | 分类于 ，

题目：

　　给定一个整数数组，判断是否存在重复元素。
　　如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

思路：

　　涉及数组中元素的次数，一般会想到利用哈希表记录元素个数。同时此题也可先排序，再比较相邻元素是否有相同。

代码：

1.哈希表：

1
2
3
4
5
6
7
8
9
10
 public boolean containsDuplicate(int[] nums) {
     Set<Integer> set = new HashSet<>();
     for(int num:nums) {
     	if (set.contains(num)) {
	return true;
}
     	set.add(num);
     }
     return false;
 }

2.排序：

1
2
3
4
5
6
7
8
9
 public boolean containsDuplicate1(int[] nums) {
 	Arrays.sort(nums);
 	for(int i = 0;i < nums.length-1;i++) {
 		if (nums[i] == nums[i+1]) {
	return true;
}
 	}
 	return false;
 }

复杂度分析及总结：

1.哈希表：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

2.排序：

　　时间复杂度：
　　　　O(nlogn)。
　　空间复杂度：
　　　　O(1)。