文档章节

LeetCode:Contains Duplicate II - 判断数组内是否有重复元素2

北风其凉
 北风其凉
发布于 2015/10/15 13:52
字数 628
阅读 2958
收藏 0

1、题目名称

Contains Duplicate II(判断数组内是否有重复元素2)

2、题目地址

https://leetcode.com/problems/contains-duplicate-ii/

3、题目内容

英文:Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

中文:给出一个整数数组,判断该数组内是否有两个元素值是相同的,且他们的索引值相差不大于k,是则返回true,否则返回false

4、一个TLE的方法

本题如果直接使用暴力方法解决会运行超时。一段TLE的Java代码如下:

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {
    
    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
        if (nums.length <= 1) {
            return false;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= i + k && j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

5、解题方法1

一个比较容易想到的方式是使用HashMap来完成目标,使用HashMap解决本题的方式与解决第217题的方式(Contains Duplicate)非常类似。

Java代码如下:

import java.util.HashMap;

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {
    
    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
        if (nums.length <= 1) {
            return false;
        }

        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i]) && i - hashMap.get(nums[i]) <= k) {
                return true;
            }
            hashMap.put(nums[i], i);
        }
        
        return false;
    }
}

6、解题方法2

另一种方式是使用HashSet来解决本问题。HashSet是使用HashMap实现的集合。在HashSet的add函数中,如果被插入的元素已存在,则返回true,否则返回false。下面的Java代码就是利用了HashSet的这个性质:

import java.util.HashSet;

/**
 * @功能说明:LeetCode 219 - Contains Duplicate II
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月15日
 */
public class Solution {

    /**
     * 查看数组内是否有重复元素且相邻重复元素索引间隔不大于K
     * 
     * @param nums
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        if (nums.length <= 1) {
            return false;
        }

        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                hashSet.remove(nums[i - k - 1]);
            }
            if (!hashSet.add(nums[i])) {
                return true;
            }
        }

        return false;
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 116
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
LeetCode:Contains Duplicate - 判断数组内是否有重复元素

1、题目名称 Contains Duplicate(判断数组内是否有重复元素) 2、题目地址 https://leetcode.com/problems/contains-duplicate/ 3、题目内容 英文:Given an array of integers, find if t...

北风其凉
2015/10/13
947
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
73
0
287. Find the Duplicate Number。

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only o......

Leafage_M
2018/01/26
0
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意:判断数组中是否有重复元素 思路:构造一个set,不重复就加进去,重复返回true,如果数据量大的话,可以用布隆过滤器 Java实现:...

yysue
2018/07/18
0
0
玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set和map 容器类 屏蔽实现细节 了解语...

天涯明月笙
2017/09/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

看过上百部片子的这个人教你视频标签算法解析

本文由云+社区发表 随着内容时代的来临,多媒体信息,特别是视频信息的分析和理解需求,如图像分类、图像打标签、视频处理等等,变得越发迫切。目前图像分类已经发展了多年,在一定条件下已经...

腾讯云加社区
32分钟前
2
0
2. 红黑树

定义:红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树(Binary Search Tree)。 要理解红黑树,先要了解什么是二叉查找树。在上一章中,我们学习了什么是二叉树,以及二叉树...

火拳-艾斯
34分钟前
2
0
input的button类型,点击页面跳转

一、input type=button 不做任何操作 例如: <input type="button" class="btn btn-primary" style="width: 30%" value="返回" onclick="window.location.href='/users/list'"></input> onc......

Sunki
40分钟前
1
0
踩坑:js 小数运算出现精度问题

背景 在学习小程序商城源码时发现了这个问题,单价可能出现小数,小数之间运算结果会莫名其妙多出一大串数字,比如下面这样👇。 在此之前我是知道 js 中著名的 0.1 + 0.2 != 0.3 的问题的,...

dkvirus
45分钟前
2
0
zookeeper和HBASE总结

zookeeper快速上手 zookeeper的基本功能和应用场景 zookeeper的整体运行机制 zookeeper的数据存储机制 数据存储形式 zookeeper中对用户的数据采用kv形式存储 只是zk有点特别: key:是以路径...

瑞查德-Jack
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部