力扣数据结构入门专栏分析 ①

力扣数据结构入门专栏分析 ①

一、题目描述

题目链接 217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同 返回 false 。

示例 1

输入 nums [1,2,3,1]输出 true示例 2

输入 nums [1,2,3,4]输出 false示例 3

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

提示

1 nums.length 105-109 nums[i] 109

题目来源 力扣 LeetCode 链接 https://leetcode-cn.com/problems/contains-duplicate著作权归领扣网络所有。商业转载请联系官方授权 非商业转载请注明出处。

二、思路分析

这道题考察了什么思想 你的思路是什么

看到这道题 我的第一想法是再建立一个数组arr 遍历整数数组 nums 然后每次将获取的元素与arr中值进行比较 如果没有就放入arr中 如果有就返回false。遍历nums完就返回true。

做题的时候是不是一次通过的 遇到了什么问题 需要注意什么细节

用上面的思路结果超时了....后来发现我们可以先排序 然后比较相邻的两个元素是否相等。还可以使用Java的HashSet的不可添加重复元素特性来完成这道算法题。

有几种解法 哪种解法时间复杂度最低 哪种解法空间复杂度最低 最优解法是什么 其他人的题解是什么 谁的效率更好一些 用不同语言实现的话 哪个语言速度最快

解法一 排序时间复杂度 O(NlogN)
空间复杂度 O(logN)
解法二 Java使用HashSet
时间复杂度 O(N)O(N)
空间复杂度 O(N)O(N)

三、AC 代码

C

int cmpfunc (const void * a, const void * b)

{

  return ( *(int*)a - *(int*)b );

}

 

bool containsDuplicate(int* nums, int numsSize) {

   qsort(nums, numsSize, sizeof(int), cmpfunc);

   for (int i 0; i numsSize - 1; i ) {

       if (nums[i] nums[i 1]) {

           return true;

       }

   }

   return false;

}

Java

class Solution {

   public boolean containsDuplicate(int[] nums) {

       Arrays.sort(nums);

       for (int i 0; i nums.length-1; i ) {

           if (nums[i] nums[i 1]) {

               return true;

           }

       }

       return false;

   }

}

Java

class Solution {

   public boolean containsDuplicate(int[] nums) {

       Set Integer set new HashSet Integer ();

       for (int x : nums) {

           if (!set.add(x)) {

               return true;

           }

       }

       return false;

   }

}

四、总结

这不是什么难题 但是当实际问题中遇到数据的量比较大时 我那种暴力算法就会超时 稍微改进一下可以将数组进行排序 然后比较相邻的的数是否有重复的 也没必要比较两边的 只需要比较后面那个即可。HashSet也是个好东西 有机会学一下。这个HashSet的add方法其实底层就是调用HashMap的put方法 不过与HashMap的put有些不同 put时如果key重复了 会覆盖原来的值 不然就返回null。而这里使用这个HashSet的add方法 如果添加时key没有重复 就返回true 否则返回false。