likes
comments
collection
share

LeetCode.217 存在重复元素

作者站长头像
站长
· 阅读数 14

题目描述:

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

总结

这题太简单了,我又会了 😊

类似的题目可以参考这个 题解

参考

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

转载自:https://juejin.cn/post/6994730061798572040
评论
请登录