LeetCode算法题-Contains Duplicate(Java实现)


这是悦乐书的第192次更新,第196篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第52题(顺位题号是217)。给定一个整数数组,查找数组是否包含任何重复项。如果数组中至少出现两次值,则函数应返回true,如果每个元素都不相同,则返回false。例如:

输入:[1,2,3,1]
输出:true

输入:[1,2,3,4]
输出:false

输入:[1,1,1,3,3,4,3,2,4,2]
输出:true

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

使用两层for循环,外层控制当前元素,内层控制剩下的元素,依次比较,发现重复元素即可返回false。

此解法的时间复杂度是O(n^2),空间复杂度是O(1)。

public boolean containsDuplicate(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    for (int i=0; i < nums.length; i++) {
        for (int j=i+1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}


03 第二种解法

使用HashMap,借助其put(key,value)方法,如果key在map中已经存在,则返回此key所对应的value,反之如果key不存在,返回null。所以,数组中的元素存在重复值时,进行put操作时是不会返回null的。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public boolean containsDuplicate2(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (int i=0; i < nums.length; i++) {
        if (map.put(nums[i], i) != null) {
            return true;
        }
    }
    return false;
}


04 第三种解法

使用HashSet,借助其add方法,如果当前元素已经存在则返回false,说明存在重复元素。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public boolean containsDuplicate3(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    Set<Integer> set = new HashSet<>();
    for (int i=0; i<nums.length; i++) {
        if (!set.add(nums[i])) {
            return true;
        }
    }
    return false;
}


05 第四种解法

先将数组排序,利用Arrays.sort()方法,然后使用for循环依次比较相邻的元素,如果相等,则存在重复元素。

此解法的时间复杂度是O(nlog(n)),空间复杂度是O(1)。

public boolean containsDuplicate4(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    Arrays.sort(nums);
    for (int i=0; i<nums.length-1; i++) {
        if (nums[i] == nums[i+1]) {
            return true;
        }
    }
    return false;
}


06 第五种解法

利用IntStream接口,此接口是Java8的新特性,of()方法是将其内的参数转换为Stream,distinct()方法是去掉Stream中的重复元素,count()是对Stream中的元素记数。

public boolean containsDuplicate5(int[] nums) {
    return IntStream.of(nums).distinct().count() < nums.length;                
}


07 有问题的一种解法

此解法是该道题目所有Submissions中排第一的解法,测试综合用时是1毫秒,应该是击败了100%的提交,但是该解法有一点问题。

public boolean containsDuplicate6(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    for (int i = 0; i < nums.length; i++) {
        for (int j = i - 1; j > -1; j--) {
            if (nums[i] > nums[j]) {
                break;
            } else if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

问题所在:进入内层循环时,如果当前元素大于前一个元素,那么结束内层循环,进入外层循环下一次循环。如果该重复的元素正好在其前面的元素中,那就产生了误判,例如此数组{25,2,25},当外层循环判断到第3个元素,即25时,25大于第二个元素2,直接break,进入外层循环,已经遍历完所有元素,最后返回false,但是此数组应该是要返回true的。

一个没有排过序的数组,直接判断相邻的元素来决定是否重复,很容易误判,不知道为什么此解法还能被AC。

08 小结

算法专题目前已连续日更超过一个月,算法题文章52+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!


作者:小川94,发布于:2018/12/06
原文:https://www.cnblogs.com/xiaochuan94/p/10073849.html