LeetCode第217题,难度简单。
原题地址:https://leetcode-cn.com/problems/contains-duplicate/
题目描述:
给定一个整数数组,判断是否存在重复元素。
如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
解题思路:
这个题目有好几种方法:
第一种,位图法。会占用很多的空间,但是只需要一次遍历,属于典型的空间换时间。实现就是自己定义一个HashMap,然后往里面不停的放数字即可。
第二种,HashSet。类似位图法,同样会占用很多空间,也只需要一次遍历。实现很简单,直接将数组写入HashSet,然后判断集合大小是否发生变化即可。
第三种,暴力遍历法。粗暴的双重遍历每个元素,不需要额外的空间,但是时间会很长。
第四种,先排序,然后判断相邻元素是否相等。时间不会太长,空间可能会占用一点。
中文官网题解:
https://leetcode-cn.com/problems/contains-duplicate/solution/
个人题解:
.public class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums.length == 0 || nums.length == 1)
return false;
Arrays.sort(nums);
int j = nums[0];
for(int i = 1; i < nums.length; i++){
if(j == nums[i])
return true;
j = nums[i];
}
return false;
}
}
结果:
我采用的是第四种方法,速度还算可以。不过前两种方法速度应该会更快。