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

题目

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)：
i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
示例 2：
输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。
提示：
2 <= nums.length <= 105
-109 <= nums[i] <= 109
1 <= indexDiff <= nums.length
0 <= valueDiff <= 109

滑动窗口+有序集合

代码

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;
}
};

分析

如果(i,j)符合，则(j,i)也符合。所以可以只考虑i<j，不考虑i>j。题意明确表示i!=j。所以只需要考虑i<j。用有序集合表示滑动窗口nums[max(0,j-k),j]。其实用set就可以了，multiset可以少一个判断：如果存在重复值直接返回true。

桶排序

用桶来表示滑动窗口。设置桶的大小为valueDiff+1，如果2个数在同一个桶中说明符合。如果符合直接返回，所以一个桶不会存在两个像素。可以用哈希映射来表示桶。如果不在一个桶，还要比较是否和前一个桶或后一桶符合条件。

代码

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);
}
};