【Leetcode 220】 Contains Duplicate III

问题描述：判断数组中是否存在<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;

    }

};

就这样了，加油。

巴特西

【Leetcode 220】 Contains Duplicate III

最新文章

热门文章