首页技术正文

【Leetcode 220】 Contains Duplicate III

程序员冠英技术 2022年11月17日

0 收藏 403 点赞 2,597 浏览 1014 个字

问题描述：判断数组中是否存在<ai aj> abs(ai – aj)<=t && abs(i – j) <=k；

问题分析：需要一个数据结构来维护满足条件k。单纯暴力，会超时。假设当前元素num[i]我只需要判断 i- k -1 到 i之间的元素的关系就可以了。假设当前元素是num[i], 另一个元素a（multiset中的）,他们满足

　　| a – num[i]|<=t 　　　　可得到　　　　num[i] – t <= a <= num[i] + t。

　　所以我需要尽快找到 num[i] – t 的下界（lb）（第一个大于等于 num[i] – t的值）然后在判断 |lb – num[i]| <= t是否满足。

问题解决：这里使用multiset来维护最多k个元素。区别与set ， multiset可以存储多个相同的元素。然后按照升序关系排列。

PS：C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html

PSS: 关于 lower_bound() 和 upper_bound() ,看这里http://www.cnblogs.com/cobbliu/archive/2012/05/21/2512249.html

最后代码：

class Solution {
public:
      bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
      {
            if(nums.size() ==  || k == ) return false;
            multiset<int>muset;//可重复元素的set
            for(int i = ; i < nums.size(); i ++){
                  if(muset.size() >= k + )
                        muset.erase(nums[i - k  - ]);
                  auto lb = muset.lower_bound(nums[i] - t);//第一个大于等num[i]的元素位置
                  if(lb != muset.end() && abs(*lb - nums[i]) <= t) return true;
                  muset.insert(nums[i]);
            }
            return false;
    }
};

就这样了，加油。