LeetCode.217 存在重复元素-一一网

这是我参与8月更文挑战的第10天，活动详情查看：8月更文挑战

题目描述：

217. 存在重复元素 – 力扣（LeetCode） (leetcode-cn.com)

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例一

输入: [1,2,3,1]
输出: true
复制代码

示例二

输入: [1,2,3,4]
输出: false
复制代码

示例三

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
复制代码

思路分析

排序

这个也很简单，排序之后，如果有重复的元素，那么一定是相邻的。

所以我们只要排序后，遍历比较相邻的两个元素是否相等就行了。

注意：

这里排序直接使用 Java 底层提供的 sort 就行了，自己写的一般打不过 – –

AC代码

class Solution {
    fun containsDuplicate(nums: IntArray): Boolean {
        Arrays.sort(nums)
        
        for (i in 0..nums.lastIndex - 1) {
            if (nums[i] == nums[i+1]) {
                return true
            }
        }
        return false
    }
}

复制代码

哈希表

这里我们还是老套路，利用 set 不可添加重复元素的特性

我们可以遍历数组，把元素插入到哈希表中，如果添加失败就代表重复了。

还可以都插入完，比较下哈希表和原数组的长度，如果不等，代表有元素重复了。

这里注意如果用 kotlin 解题的话，有很多的高阶语法可以使用

但是代码并不是越短越好，有的一行代码时间复杂度和空间复杂度都不低。

AC代码

class Solution {
    fun containsDuplicate(nums: IntArray): Boolean {
        return nums.size > nums.toSet().size
    }
}
复制代码

class Solution {
    fun containsDuplicate(nums: IntArray): Boolean {
        //distinct() 去重 其实内部也是转set实现的
        return nums.size > nums.distinct().count()
    }
    
}
复制代码

class Solution {
    fun containsDuplicate(nums: IntArray): Boolean {
         val set = hashSetOf<Int>()
        for (n in nums){
            if(!set.add(n)) {
                return true
            }
        }
        return false
    }
}
复制代码