Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the absolute difference between i and j is at most k.
Solution 1: use multimap to store the num:index in the order of increasing num. use it2 to point to the previous element of it. The time complexity is O(nlog(n)). Note that the iterator here only can increase like ++,can't decrease like --.
1 class Solution { 2 public: 3 bool containsNearbyDuplicate(vector<int>& nums, int k) { 4 multimap<int,int> m; 5 int n=nums.size(); 6 for (int i=0;i<n;i++){ 7 m.insert(pair<int,int>(nums[i],i)); //num:index 8 } 9 multimap<int,int>::iterator it2=m.end(); 10 for (multimap<int,int>::iterator it=m.begin();it!=m.end();it++){ 11 if (it2!=m.end()){ 12 if ((*it).first==(*(it2)).first && ((*it).second-(*(it2)).second)<=k) return true; 13 } 14 it2=it; 15 } 16 return false; 17 } 18 };
转载于:https://www.cnblogs.com/anghostcici/p/6673896.html
相关资源：垃圾分类数据集及代码