前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-219-Contains Duplicate II(使用set来判断长度为k+1的闭区间中有没有重复元素)

leetcode-219-Contains Duplicate II(使用set来判断长度为k+1的闭区间中有没有重复元素)

作者头像
chenjx85
发布2019-03-14 17:15:53
5780
发布2019-03-14 17:15:53
举报
文章被收录于专栏:chenjx85的技术专栏

题目描述:

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.

Example 1:

代码语言:javascript
复制
Input: [1,2,3,1], k = 3
Output: true

Example 2:

代码语言:javascript
复制
Input: [1,0,1,1], k =1
Output: true

Example 3:

代码语言:javascript
复制
Input: [1,2,1], k =0
Output: false

要完成的函数:

bool containsNearbyDuplicate(vector<int>& nums, int k) 

说明:

1、这道题给定一个vector和一个整数k,要求判断能不能找到两个不同位置的相同元素,他们的位置分别是i和j,使得i-j的绝对值不超过k。

2、这道题相比起上一道“找到两个重复的元素”,增加了距离k的限制。

首先,我们能够判断如果k<=0,那么必定是不存在两个不同位置的相同元素的。

其次,如果k>=nums.size()-1,那么这道题也就是上一道“找到两个重复的元素”的做法。

所以我们只需要关注k<nums.size()这种情况下,我们要如何判断。

最简单最暴力的方法当然是双重循环,设定窗口长度为k+1,从nums的第一位开始,判断窗口内有没有跟首元素相同的元素。

接着窗口不断往后挪,去掉第一个元素,增加一个新的元素,判断窗口的首元素,也就是这时候nums的第二个元素,有没有在窗口内出现重复元素。

这种做法时间复杂度O(n^2)

我们也可以仍然往后挪窗口,只不过使用set,用哈希的方法来判断窗口中有没有重复元素,这种判断比起上述暴力方法快了许多。

时间复杂度大致是O(n),因为哈希的时间时间复杂度是O(1)?

代码如下:(附详解)

代码语言:javascript
复制
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        int s1=nums.size();
        if(k<=0)//边界条件
            return false;
        if(k>=s1-1)//转化为上一道题,“找到两个重复的元素”
        {
            sort(nums.begin(),nums.end());
            for(int i=0;i<s1-1;i++)
            {
                if(nums[i]==nums[i+1])
                    return true;
            }
            return false;
        }
        unordered_set<int>set1(nums.begin(),nums.begin()+k+1);//使用set来存储,初始化其中有k+1个元素
        if(set1.size()!=k+1)//初始情况下的判断
            return true;
        for(int i=k+1;i<s1;i++)
        {
            set1.erase(nums[i-k-1]);//删去首位元素
            set1.insert(nums[i]);//增加后一位新的元素,这个插入过程其实包含了判断有没有重复,决定要不要插入到set中
            if(set1.size()!=k+1)//用set的size来判断
                return true;
        }
        return false;
        
    }

上述代码实测24ms,beats 97.46% of cpp submissions。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-05-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档