最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇1_存在重复元素解题思路

XAMPP相关 admin 371浏览 0评论

来源:LeetCode

难度:简单

描述:

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

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

drf031

 

drf0031

分析:该题可以直接两层循环判断即可,也可采用哈希表的方式来解

题外话:采用空间换时间还是时间换空间主要取决于咱们的服务哪类资源比较富裕,例如内存富裕就尽量用空间来换取时间,反之就尽量用时间换空间

解题

方法一:哈希表法(两重循环代码就不写了)

思路:通过set存储每个元素,当发现添加元素的时候set的大小不变,即说明有重复元素

 

代码:

 1public boolean containsDuplicate(int[] nums) {
 2    if (nums == null || nums.length < 2) {
 3        return false;
 4    }
 5    Set<Integer> set = new HashSet<>();
 6    for (int num : nums) {
 7        int size = set.size();
 8        set.add(num);
 9        //利用set去重性,前后大小一样代表set已经存在该元素
10        if (size == set.size()) {
11            return true;
12        }
13    }
14    return false;
15}

进阶版:给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。

 

示例1:

drf00031

示例2:

drf000031

分析:题目在原来判断相等的基础上增加了限制,即相等的两个元素下标距离必须在k之内,同样我们可以两层循环解,也可以通过哈希表记录元素以及对应下标的关系来解

方法一:Map存储下标法

思路:利用map存储元素以及元素的下标,当元素已存在时,比较两者下标差值是否小于k,小于则返回true,否则将最新的下标覆盖原来的下标

 

代码:

 1public boolean containsDuplicate(int[] nums, int k) {
 2    if (nums == null || nums.length < 2) {
 3        return false;
 4    }
 5    Map<Integer, Integer> map = new HashMap<>();
 6    for (int i = 0; i < nums.length; i++) {
 7        Integer index = map.get(nums[i]);
 8        if (index == null) {
 9            //map不存在该元素,直接添加
10            map.put(nums[i], i);
11        } else if (i - index <= k) {
12            //map已经存在该元素且上次出现和此次距离小于k
13            return true;
14        } else {
15            //存在元素但相距大于k,直接用此次的下标服务原来的下标
16          //(老的下标没有和后续元素比较意义了)
17            map.put(nums[i], i);
18        }
19    }
20    return false;
21}

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇1_存在重复元素解题思路

您必须 登录 才能发表评论!