剑指offer-03

剑指offer-03 数组中重复的数字

题目

结果

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.add(i)) {
                return i;
            }
        }
        return 0;
    }
}

上面代码的时间复杂度是O（n）。最开始，我的代码是这样的：

class Solution {
    public int findRepeatNumber(int[] nums) {
        List<Integer> list = new LinkedList<>();
        for (int i : nums) {
            if (list.contains(i)) {
                return i;
            } else {
                list.add(i);
            }
        }
        return 0;
    }
}

思路和用集合set是一样的，但是这种方法超时了，原因是list的contains方法本身也有O（n）的时间复杂度。但是set不一样，set内部是用HashMap实现的，查找的时间复杂度只有O（1）。

值得一提的是，set的add方法有一个布尔类型的返回值，如果添加失败（集合中已经存在这样的元素）会返回false，否则返回true，这一点是我之前所不知道的，可以善加利用。