217. 存在重复元素

发表于   |   分类于 LeetCode   |   本文已被浏览 678 次   |   暂无评论

描述

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

解题思路

该问题首先想到的方法应该是先对数组排序，然后在判断是否包含重复的值。但该问题的标签中包含哈希表，提醒我可以用hashset给数组去重，然后根据hashset的长度以及原始数组的长度判断是否存在重复的元素。

代码如下：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        return set.size() < nums.length;
    }
}

结果

20:06    info
        解答成功:
        执行耗时:9 ms,击败了26.19% 的Java用户
        内存消耗:45.8 MB,击败了6.29% 的Java用户

官方题解

排序

在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

哈希表

对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。
class Solution {

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    for (int x : nums) {
        if (!set.add(x)) {
            return true;
        }
    }
    return false;
}

}

小结

与题解相比，在元素add进入hashset时，可以通过add()的返回值提前终止函数，不必等到最后比较长度

添加新评论