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)


相关推荐

  • JDK下载安装及环境变量配置的图文教程(详解)「建议收藏」

    JDK下载安装及环境变量配置的图文教程(详解)「建议收藏」学习Java,需要下载并安装JDK(JavaDevelopmentKit,Java开发工具包);而为了能够快捷打开java程序,就需要按照操作系统的要求进行环境变量的配置。一、下载并安装JDK(一)下载JDK搜索“jdk官方下载”或是直接进入Sun公司的官网(https://www.oracle.com/)…

  • loadrunner的使用步骤_简单介绍一种你在家中使用过的工具

    loadrunner的使用步骤_简单介绍一种你在家中使用过的工具使用LoadRunner对登录做并发测试

    2022年10月14日
  • 音频功放的种类和基本原理

    音频功放的种类和基本原理音频功放的种类和基本原理作者:AirCity2019.12.2Aircity007@sina.com本文所有权归作者Aircity所有1 简介功率放大器简称功放,它是将小信号放大,这个放大包括电压和电流,用更大的功率推动音响放声。在技术发展过程中,产生了不同类型的功放种类,按照功率管的导电方式,可以分为甲类功放(又称A类)、乙类功放(又称B类)、甲乙类功放(又称AB类)和丁类功放功…

  • dpkg安装软件流程_DPKG命令与软件安装、APT[通俗易懂]

    dpkg安装软件流程_DPKG命令与软件安装、APT[通俗易懂]====Linux软件包====Linux系统中,软件通常以源代码或者预编译包的形式提供。软件的源代码通常需要编译为二进制代码才可使用,安装比较耗时。用户可以自行调节编译选项,决定需要的功能或组件,或者针对硬件平台作一些优化预编译包通常由软件发布者进行编译,用户只要将预编译包拷贝到系统中即可。考虑到预编译包的通用性,预编译包一般不会针对某种硬件平台优化,所包含的功能和组件也是通用的组合。ubunt…

  • CentOS安装图形界面

    CentOS安装图形界面VmwareCentOS图形界面

  • tof 相机的数据读取,depth data和amplitude data以及3D数据[通俗易懂]

    tof 相机的数据读取,depth data和amplitude data以及3D数据[通俗易懂]1.开发前提如果相机带有SDK也就是开发需要的工具以及包,就要用相机带的开发包,里面包含了相应的读取文件的函数,以及设置的相机的相关函数。本文使用的是TTF相机,C++头文件代码如下:#include"../../include/TTF_API.h"#include&lt;unistd.h&gt;usingnamespacestd;usingnamespaceV…

发表回复

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

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