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

其它

测试环境

操作系统：win7 开发环境： VS2019 **C+

+17**

相关下载

如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版