[leetcode]217.存在重复元素

[MagicalBridge]

方法一：排序

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
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为数组的长度，注意在这里我们应当考虑递归调用栈的深度

方法二：哈希表

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
  const set = new Set();
  for (const x of nums) {
    if (set.has(x)) {
      return true;
    }
    set.add(x);
  }
  return false;
};

复杂度分析:

• 时间复杂度：O(N),其中N为数组的长度。
• 空间复杂度：O(N),其中N为数组的长度。