返回信息流题目是看一个数组中有没有重复的数
解法一：快速排序，然后挨个看数字是不是与前一个一样，时间复杂度应该是O(nlogn)
解法二：建一个HashSet，依次把数存进去，然后每存一个之前用contains()查是否存在过这个数，时间复杂度应该是O(n)
结果Leetcode上解法一快很多是神马情况……
解法一：
public class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums.length==0)return false;
Arrays.sort(nums);
int a = nums[0]-1;
for(int i=0;i<nums.length;i++){
if(a==nums[i])return true;
a=nums[i];
}
return false;
}
}
速度超过81.45%
解法二：
public class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i = 0;i<nums.length;i++){
if(set.contains(nums[i]))return true;
set.add(nums[i]);
}
return false;
}
}
速度超过30.21%
这是一条镜像帖。来源：北邮人论坛 / java / #48111同步于 2016/3/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
求问HashSet的时间复杂度
zhouyanbl
2016/3/1镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
【 在 Lamperouge 的大作中提到: 】
: new hashSet<>(nums.length)
现在觉得应该是Leetcode有的数据量太小体现不出HashSet优越性吧……