知识点
哈希,枚举
思路
首先,我们使用map<int,vector>来建立点的编号到对应编号所在的位置之间的映射(有序):
对样例:1 2 3 1
1 | 0,3 |
2 | 1 |
3 | 2 |
然后,对每个相同编号的vector进行遍历,若存在vector[i]-vector[i-1]<=K,则说明题意所求存在,返回true。否则不存在,返回false
代码
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param weights int整型vector
* @param n int整型
* @param k int整型
* @return bool布尔型
*/
bool checkDuplicate(vector<int>& weights, int n, int k) {
// write code here
map<int,vector<int>>t;
for(int i=0;i<n;i++)
{
t[weights[i]].push_back(i);
}
for(auto v:t)
{
for(int i=1;i<v.second.size();i++)
{ // cout<<v.first<<" "<<v.second[i]<<" "<<v.second[i-1]<<endl;
if(v.second[i]-v.second[i-1]<=k)return true;
}
}
return false;
}
};
```