LeetCode219:Contains Duplicate II

LeetCode219:Contains Duplicate II

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Given an array of integers and an integer k, find out whether there 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.

直接使用循环时间复杂度为O(N*k),使用stl中的基于红黑树实现的map能降低循环的时间,在O(logN)的时间复杂度内找到元素。或者更进一步使用基于hash表的unordered_map。在常数时间内找到元素。这道题学习到的两个经验:

  1. 当想在常数时间内完毕查询工作时考虑hash表。

  2. stl中实用hash表实现的数据结构map和set,所以它们也保留了hash表查询上的特点。

代码例如以下:

class Solution {
public:

/* 解法一:超时 bool containsNearbyDuplicate(vector<int>& nums, int k) { int length=nums.size(); if(length<=1||k<=0) return false; //将每个元素与其后面k个元素进行比較 for(int i=0;i<length;i++) { for(int j=1;j<=k&&(i+j)<length;j++) { if(nums[i]==nums[i+j]) return true; } } return false; } */


   //解法二,利用stl中的map。记录下整数以及它的下标 
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        //之前直接使用的是map。时间是96ms,后来把map替换成unordered_map时间变成了32ms
        unordered_map<int ,int> maps;
        int length=nums.size();
        for(int i=0;i<length;i++)
        {
            if(maps.count(nums[i]))//假设在maps中找到了该元素。推断它们位置是否小于等于k
            {
                if((i-maps[nums[i]])<=k) 
                    return true;
            }
            maps[nums[i]]=i;
        }
        return false;
    }

};

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117015.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MessageDigest 详解

    MessageDigest 详解一、概述java.security.MessageDigest类用于为应用程序提供信息摘要算法的功能,如MD5或SHA算法。简单点说就是用于生成散列码。信息摘要是安全的单向哈希函数,它接收任意大小的数据,输出固定长度的哈希值。关于信息摘要和散列码请参照《数字证书简介》MessageDigest 通过其getInstance系列静态函数来进行实例化和初始化。MessageDi

  • SpringBoot跨域设置(CORS)「建议收藏」

    SpringBoot跨域设置(CORS)「建议收藏」目录什么是跨域跨域资源共享(CORS)1.简单请求2.非简单请求SpringBoot设置CORS1.配置过滤器CorsFilter2.实现接口WebMvcConfigurer3.使用注解@CrossOrigin什么是跨域请求url的协议、域名、端口三者有任意一个不同即为跨域。跨域问题是因为浏览器的同源策略的限制而产生的。同源:请求url的协议、域名、端口三者都相同即为同源(同一个域)。同源策略:同源策略(Sameoriginpolicy)是一种约定,他是浏览器最核心也最基本的安全

  • kubernetes可以实现容器集群的哪些功能_hadoop高可用集群搭建

    kubernetes可以实现容器集群的哪些功能_hadoop高可用集群搭建二进制方式部署Kubernetes高可用集群文章目录二进制方式部署Kubernetes高可用集群1.环境准备1.1.Kubernetes高可用集群部署方式1.2.Kubernetes集群弃用docker容器1.3.Kubernetes集群所需的证书1.4.环境准备1.5.安装cfssl证书生成工具2.操作系统初始化配置3.部署Etcd集群3.1.使用cfssl证书工具生成etcd证书3.2.部署etcd集群4.部署Docker服务4.1.安装docker4.2.为docker创建systemctl启动脚本

  • 《Storm企业级应用:实战、运维和调优》——1.3 Storm核心组件[通俗易懂]

    《Storm企业级应用:实战、运维和调优》——1.3 Storm核心组件

  • JavaScript 判断元素是否在数组中

    JavaScript 判断元素是否在数组中

    2021年11月22日
  • 下拉刷新Demo[通俗易懂]

    下拉刷新Demo[通俗易懂]引用了网上的demo。packagecom.news.utils;importjava.text.SimpleDateFormat;importjava.util.Date;importcom.news.todaynews.R;importandroid.content.Context;importandroid.util.AttributeSet;impor

    2022年10月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号