注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex219 Contains Duplicate II  

2015-05-31 17:28:33|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
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 iand j is at most k.

包含重复元素,并且存在下标距离最大是k,开始的把题目看错了,以为所有的i,j的距离都是至多k呢!!提交了好几次都错了~~easy题。
其实下面的代码可以继续精简,one pass就能得到结果,下标的肯定是递增的,计算每次来的下标和最后一个下标的差值,如果小于k就返回true了,这样效率更高,懒得改动了。

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k){
int i = 0;
map<int, vector<int>>myMap;
vector<int>tmp;
bool part = false;
for (i = 0; i < nums.size(); i++)
{
myMap[nums[i]].push_back(i);
}
map<int, vector<int>>::iterator it;
for (it = myMap.begin(); it != myMap.end(); it++)
{
tmp = (*it).second;
sort(tmp.begin(), tmp.end());
if (tmp.size() >= 2 && valid(tmp,k))
return true;
}
return false;
}
bool valid(vector<int> nums, int k)
{
int i, j;
for (i = 1; i < nums.size(); i++)
{
if ((nums[i] - nums[i - 1] <= k))
return true;
}
return false;
}
};


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017