LeetCode、217存在重复元素

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

前言

受“王鱼”同学的点拨，从昨天开始刷LeetCode Top精选面试题，为冲击秋招做准备。

题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

玩一下~

解题思路：数组转Set去重。Set的size 和数组length相等，无重复元素。不等，有重复元素

var containsDuplicate = function(nums) {
    return new Set(nums).size !== nums.length
};
复制代码

哈哈哈，有人说你这是什么啊，我也会，别急，先热个身嘛，来，力扣刷刷的思路虽迟但到~

排序

解题思路：在对数字从小到大排序之后。数组的重复元素一定出现在相邻的位置，因此我们可以扫描已经排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

var containsDuplicate = function(nums) {
  // 将数组做升序排列
  nums.sort((a, b) => a - b);
  // 数组的长度
  const n = nums.length;
  // 循环遍历数组 因为下面需要有 i+1的操作，所以这里n-1是取不到的。
  for (let i = 0; i < n - 1; i++) {
    if (nums[i] === nums[i + 1]) {
      return true;
    }
  }
  return false;
};
// 时间复杂度： O(NlogN)，其中N为数组的长度。需要对数组进行排序。
// 空间复杂度： O(logN),其中N为数组的长度，注意在这里我们应当考虑递归调用栈的深度
复制代码

哈希map

解题思路：对于数组中的每个元素，我们将它插入到哈希表中，如果插入一个元素的时候发现这个元素已经存在于哈希表中，则说明存在重复的元素。

var containsDuplicate = function(nums) {
 const map = new  Map()
 for(let i of nums) {
     if(map.has(i)){
         return true
     } else {
         map.set(i,1)
     }
 }
 return false
};
// 时间复杂度：O(N)，其中 N为数组的长度。
// 空间复杂度：O(N)，其中 N为数组的长度。
复制代码

今日加餐

今日加餐我选择了LeetCode136、只出现一次的数，两个一起恰，味道更好嗷~

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

var singleNumber = function(nums) {
    //法1 排序后 前后比较
    nums.sort((a,b) => a - b);
    for(let i = 0; i < nums.length; i++){
        if(nums[i-1] !== nums[i] && nums[i] !== nums[i+1]) 
        return nums[i];
    }
    
    //法2 利用map
    let map = new Map();
    nums.forEach(item =>{
        map.set(item, map.has(item) ? map.get(item) + 1 : 1);
    })
    for(let [key, val] of map.entries()){
        if(val === 1) return key;
    }

    //法3 异或运算 
    return nums.reduce((pre,cur) => pre ^ cur);
};
复制代码

npy：法3的异或看不懂哇！！！

me：好好好，来给你讲解一下，然后给你说一下简单的思路哈~

首先针对异或运算，这里做一个知识点的总结：

任何数和自己做异或运算，结果为 00，即 a⊕a=0a⊕a=0 。
任何数和 00 做异或运算，结果还是自己，即 a⊕0=⊕a⊕0=⊕。
异或运算中，满足交换律和结合律，也就是 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

var singleNumber = function(nums) {
    let ans = 0;
    for(let i = 0; i < nums.length; i++){
        ans ^= nums[i];
    }
    return ans;
};
复制代码

总结

刷题打卡第8天，选择力扣第217、136题，学习了数组中的一个元素或者重复元素，一起加油哇~

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：
点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）关注公众号给npy的前端秘籍，我们一起学习一起进步。
觉得不错的话，也可以阅读其他文章（感谢朋友的鼓励与支持???）

开启LeetCode之旅

LeetCode之双指针

Leet27、移除元素

前端工程师必学的经典排序算法

LeetCode20、括号匹配

LeetCode7、整数反转

LeetCode344、反转字符串