文档章节

查找下标满足一定条件的重复 Contains Duplicate II

叶枫啦啦
 叶枫啦啦
发布于 2017/05/16 21:10
字数 519
阅读 8
收藏 0

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 absolute difference between i and j is at most k.

解决方法:

①暴力破解。直接双重循环查找满足下标之差不大于K的数是否有重复的,若有,则返回true。否则,返回false。这种方法超时。

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

②使用HashMap。将数组中的值和下标依次存储到map中,同时查找之前存入的值是否有与它相等的值,计算它们之间的距离,看是否满足要求。用时20ms。

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

若先保存到map中再查找,则会有重复的key值,无法区分满足条件的是哪些。

③使用HashSet,它在使用add()方法时,若set中不存在,则直接插入并返回true,否则,返回false。在下面的方法中使用了它的这一特性,使用set保存k个值,当插入大于k时,就删去前面的数。此时,若插入时返回false,就表示这两个相同的值在k个距离以内。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0;i <nums.length ;i ++ ) {
            if (i > k) { //使用一个滑动窗口,使用set保存这k个值,之前的值均被删除。不能加=,因为输入为[-1,-1] 1时,结果错误
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {//若添加时返回false,表示这k个值中包含该值,满足题意,返回true
                return true;
            }
        }
        //否则返回false
        return false;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
查找重复出现的数字 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......

叶枫啦啦
2017/12/20
9
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
Leetcode PHP题解--D90 217. Contains Duplicate

D90 217. Contains Duplicate 题目链接 217. Contains Duplicate 题目分析 返回给定的数组中是否有元素重复出现。 思路 用count和array_unique即可 最终代码 若觉得本文章对你有用,欢迎用爱...

skys215
06/19
14
0
LeetCode:Contains Duplicate II - 判断数组内是否有重复元素2

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

北风其凉
2015/10/15
3.1K
0
LeetCode Contains Duplicate

LeetCode Contains Duplicate Mz的博客2016-03-15173 阅读 算法C/C++ Contains Duplicate 原题传送门: https://leetcode.com/problems/contains-duplicate/ Contains Duplicate II 原题传送门......

Mz的博客
2016/03/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

刚哥谈架构 (二) 我眼中的架构师

之前在公司,有小伙伴在向别人介绍我的时候,经常会有人这么说:“刚哥是我们的architcture”,如果来人是老外,心中一定是一惊,心中暗叹,“这位匪首看上去貌不惊人,难道已经做到了架构和...

naughty
31分钟前
2
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
84
3
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
5
0
Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部