初级算法-数组-存在重复元素

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

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

摘一个示例做个说明.
示例 1：
输入: [1,2,3,1]
输出: true

条件分析:

1. 只要有两个相同则返回结果 -> 不用全部遍历完
2. !隐形条件 -> 数组可能很长

解决思路1:

1. 根据分析1,采用循环判断,用变量存储进行比较
2. 根据分析2,采用哈希表存储方式

循环时,判断存储内是否存在当前值,存在则返回,不存在则存入该值.

解决思路2:

数组内存储的是Int数据,可以对数组进行排序,再进行比较

排序数组,然后判断相邻两个数据是否相等,相等则返回true

代码实现-Swift版本:

思路1代码:

func containsDuplicate(_ nums: [Int]) -> Bool {
    /**
     时间复杂度：O(N)，其中 NN 为数组的长度。
     
     空间复杂度：O(N)，其中 NN 为数组的长度。
     */
    if nums.count < 2 {
        return false
    }
    // 不要用数组,因为数组没有字典效率高,会超时
    var dic: [Int: Int] = [:]
    for item in nums {
        let value = dic[item]
        if value != nil {
            return true
        }
        dic.updateValue(item, forKey: item)
    }
    
    return false
}

存在重复元素 哈希表 提交结果.jpg

思路2代码:

func containsDuplicate(_ nums: [Int]) -> Bool {
    if nums.count < 2 {
        return false
    }
    /**
     时间复杂度：O(N log N)，其中 N 为数组的长度。需要对数组进行排序。
     
     空间复杂度：O(log N)，其中 N 为数组的长度。注意我们在这里应当考虑递归调用栈的深度。
     */
    
    let array = nums.sorted()
    for i in 0 ..< array.count - 1 {
        if array[i] == array [i + 1] {
            return true
        }
    }
    
    return false
}

存在重复元素 数组排序 提交结果.jpg

测试用例:

// 存在重复元素
let containsDuplicateArray= [1,8,5,9,2,6,4,3,8,7]
// 不存在重复元素
let containsDuplicateArray= [1,8,5,9,2,6,4,3,7]

考察要点:

• 数组
• 哈希表
• 排序