大家好,又见面了,我是全栈君,今天给大家准备了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。在常数时间内找到元素。这道题学习到的两个经验:
- 当想在常数时间内完毕查询工作时考虑hash表。
- 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账号...