C++桶排序算法的应用：存在重复元素 III

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector& nums, int indexDiff, int valueDiff) {
std::multiset setHas;
for (int i = 0; i < nums.size(); i++)
{
const int iDelIndex = i - indexDiff - 1;
if (iDelIndex >= 0)
{
auto it = setHas.find(nums[iDelIndex]);
setHas.erase(it);
}
auto it1 = setHas.lower_bound(nums[i] - valueDiff);
auto it2 = setHas.upper_bound(nums[i] + valueDiff);
if (it1 != it2)
{
return true;
}
setHas.emplace(nums[i]);
}
return false;
}
};

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
unordered_map<int, int> mp;
int n = nums.size();
for (int i = 0; i < n; i++)
{
const int curValue = nums[i];
int inx = GetBucketIndex(curValue, t + 1);
if (mp.count(inx))
{
return true;
}
if (mp.count(inx - 1) && (abs(curValue - mp[inx - 1]) <= t))
{
return true;
}
if (mp.count(inx + 1) && (abs(curValue - mp[inx + 1]) <= t))
{
return true;
}
mp[inx] = curValue;
if (i>= k)
{
const int iEraseIndex = GetBucketIndex(nums[i - k ],t+1);
mp.erase(iEraseIndex);
}
}
return false;
}
int GetBucketIndex(int value, int iBuckCap)
{
return value >= 0 ? (value / iBuckCap) : ((value + 1) / iBuckCap - 1);
}
};