存在重复元素

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

LeetCode每日一题，217. Contains Duplicate

先看题目描述

rZxhOH.png

题目大意就是给定一个数组，让我们判断其中是否存在重复元素

算法和思路

排序后比较

可以先将数组排序，然后比较相邻元素即可

哈希表

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

算法源码

排序后比较

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

哈希表

1
2
3
4
5
6
7
8
9
10
11
12

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;
    }
}

下面是这个是自己一开始实现的哈希表解法的源码，效率是没有上面这个快的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> nums_set = new HashSet<Integer>();
        for (int num : nums) {
            if (nums_set.contains(num)) {
                return true;
            }
            nums_set.add(num);
        }
        return false;
    }
}

下面这个是看的运行效率比较靠前的代码，其实整体思路和哈希表差不多，只不过这里使用了一个布尔数组，效率更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return false;
        }
        int min = nums[0];
        int max = nums[0];
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        boolean bool[] = new boolean[max - min + 1];
        for (int num : nums) {
            if (bool[num - min]) {
                return true;
            }
            bool[num - min] = !bool[num - min];
        }
        return false;
    }
}