【算法-初级-数组】存在重复元素(JavaScript实现)

【算法-初级-数组】存在重复元素(JavaScript实现)

博客说明

文章所涉及的部分资料来自互联网整理,当然还有自己个人的总结和看法,分享的目的在于共建社区和巩固自己。引用的资料如有侵权,请联系本人删除!幸好我在,感谢你来!

算法说明

语言只是实现算法的一种手段,思路才是最为重要的。

如果有多种解法的话,只选一种语言作为解答对比。

如果单独将某一种算法的话,会以多种语言实现,对比语言的特性。

😎因为多对多的话,篇幅会拉的比较大,影响观看体验!

题目

题目地址

217. 存在重复元素

题目说明

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

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

示例 1

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

示例 2

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

示例 3

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

思路

暴力解法

怎么能缺少暴力解法呢,这毕竟是大脑最直白的想法,当然保留!😁

直接遍历,拿一个辅助数组,一个一个往里面塞,直到遇到相等的,那么就是它!

这里就不贴代码了(暴力的解法毕竟不美观哈!),看一下结果!

image-20211226144133904

但注意哈!不可耻!毕竟通过了✅。

排序

思路

在暴力解法的时候遇到了一个问题,就是时间和空间复杂度都比较高。

因为在辅助数组里面也需要遍历,因为原数组的不是按照顺序来的,所以需要我们来一场排序,会解决掉一些问题。

因为重复的元素都会在相邻的位置,只需要当前的元素左右扭头看一下即可。

JavaScript

之前是用的js写的暴力,所以对比js的排序改进版。

看下面的图,发现然而并没卵用,该高还是得高,时间有那么一点改进。

😶因为排序也是需要开销的。

再来!

image-20211226145445536

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    if (nums.length < 1) return false
    // 排序
    nums.sort((a, b) => a - b)
    const n = nums.length;
    for (var i = 0; i < n - 1; i++) {
        if (nums[i] === nums[i + 1]){
            return true
        }
    }
    return false
};

复杂度分析

时间复杂度

O(NlogN),其中 N 为数组的长度。

需要对数组进行排序。

空间复杂度

O(logN),其中 N 为数组的长度。

哈希表

思路

看我们暴力解法的时候,有两个比较麻烦的点,一个是不确定重复的元素的出现的位置(所以上一步来了排序),一个是需要辅助的数组来记录。

这次就利用哈希表来存储已遍历的元素,再次插入相同的元素的时候哈希表就能给出反应,只需要遍历就行!

JavaScript

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    if (nums.length < 1) return false
    // 哈希表
    const set = new Set();
    const n = nums.length;
    for (var i = 0; i < n; i++) {
        if (set.has(nums[i])) {
            return true
        }else {
            set.add(nums[i])
        }
    }
    return false
};

复杂度分析

时间复杂度

O(N),其中 N 为数组的长度。

空间复杂度

O(N),其中 N 为数组的长度。

感谢

万能的网络

放在LeetCode上的题解

以及勤劳的自己,个人博客GitHub测试GitHub

公众号【归子莫】,小程序【小归博客】

如果你感觉对你有帮助的话,不妨给我点赞👍吧,持续关注也行哈!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>