美文网首页
2019-01-30 第五天(#220)

2019-01-30 第五天(#220)

作者: 被子十三 | 来源:发表于2019-02-04 07:26 被阅读0次

    #220 Contains Duplicate III

    这道题想要高效实现需要二叉排序树(Binary Sort/Search Tree, BST)的数据结构。二叉树的大小随时保持和k值相同,并且在二叉树中搜索此元素。之所以使用BST是因为它的搜索效率比较高。
    现在来稍微转化一下这个问题:(j为需要搜索的元素)
    差的绝对值小于t =》
    |nums.at(i) - j| <= t
    num.at(i) + t <= j <= num.at(i) - t
    那么目标就变成搜索满足以上条件的j。
    在C++中,BST由std::set<template>实现。它和之前的unordered_set类似,唯一的区别就是其中的元素是得到了排序的。
    代码如下:

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            set<long> binary_st;
            for(int i = 0; i < nums.size(); i++) {
                if (i > k) binary_st.erase(nums[i-k-1]);
                auto pos = binary_st.lower_bound((long) nums[i] - t); 
                if (pos != binary_st.end() && t >= *pos - nums[i]) return true;
                binary_st.insert(nums[i]);
            }
            
            return false;
        }
            
    };
    

    相关文章

      网友评论

          本文标题:2019-01-30 第五天(#220)

          本文链接:https://www.haomeiwen.com/subject/wnhksqtx.html