LCR057-LCR058TreeSet和TreeMap的应用

剑指offer（专项突破版）8.4 TreeSet和TreeMap的应用

LCR057.存在重复元素

暴力解法

可以逐一扫描数组中的每个数字。对于每个数字nums[i]，需要逐一检查在它前面的k个数字是否存在从nums[i]-t到nums[i]+t的范围内的数字。如果存在，则返回true。这种思路很容易用两个嵌套的循环实现。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        // 暴力解法，双重循环
        for(int i = 0; i < n; i++){
            int j = i-k >= 0 ? i-k : 0;
            for(; j < i; j++){
                if(abs((long)nums[i] - (long)nums[j]) <= t){
                    return true;
                }
            }
        }
        return false;
    }
};

上面的代码在计算abs((long)nums[i] - (long)nums[j]时要把int转为long，在输入为[-2147483648,2147483647]时会发生溢出。

• 时间复杂度：由于数组中的每个数字都要和k个数字进行比较，如果数组的长度为n，那么这种解法的时间复杂度是O（nk）。这种解法会超出时间限制。
• 空间复杂度：O(1)

set解法

在暴力解法中其实一直在寻找是否存在落在 [nums[i] - t, nyms[i] + t] 的数，这个过程可以用平衡的二叉搜索树来加速，平衡的二叉树的搜索时间复杂度为 O(logk)。在 C+++ STL 中 set 和 map 属于关联容器，其内部由红黑树实现，红黑树是平衡二叉树的一种优化实现，其搜索时间复杂度也为 O(logk)。逐次扫码数组，对于每个数字 nums[i]，当前的 set 应该由其前 k 个数字组成，可以 lower_bound 函数可以从 set 中找到符合大于等于 nums[i] - t 的最小的数，若该数存在且小于等于 nums[i] + t，则找到了符合要求的一对数。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int> treeSet;
        for(int i = 0; i <nums.size(); i++){
            // 防止溢出
            int lowerLimit = max(nums[i], INT_MIN + t) - t;
            int upperLimit = min(nums[i], INT_MAX - t) + t;
            // 找到其中大于等于nums[i]-t的最小的数
            auto it = treeSet.lower_bound(lowerLimit);
            if(it != treeSet.end() && *it <= upperLimit){
                return true;
            }
            // 否则把当前元素放入set中
            treeSet.insert(nums[i]);
            // 删除索引差大于k的元素
            if(i >= k){
                treeSet.erase(nums[i-k]);
            }
        }
        return false;
    }
};

• 时间复杂度：做查找、添加和删除操作的时间复杂度都是O（logk），因此对于一个长度为n的数组而言，它的时间复杂度是O（nlogk）。
• 空间复杂度：treeSet，它的大小是k，因此空间复杂度是O（k）。

桶解法

换一种思路考虑该问题，因为题目只关心的是差的绝对值小于等于 t 的数字，这时候容易联想到桶，可以把数字放进若干个大小为 t + 1 的桶内，这样的好处是一个桶内的数字绝对值差肯定小于等于 t。对于桶的标号进行说明，例如 [0, t] 放进编号为 0 的桶内，[t + 1, 2t + 1] 放进编号为 1 的桶内，对于负数，则 [-t - 1, -1] 放进编号为 -1 的桶内，[-2t - 2, -t - 2] 编号为 -2 的桶内，可以发现桶

n >= 0 : ID = n / (t + 1);
n < 0 : ID = (n + 1) / (t + 1) - 1;
另外需要一个哈希表保存扫描到数字的前 k 个数字的桶的编号，key → val 为 ID → num。在算法中依次扫描数组，扫描到 nums[i]，首先得到 nums[i] 的桶ID，先查询前 k 个数字中是否也有在 ID 桶内的数字，如果存在则该数字与 nums[i] 的差的绝对值肯定小于等于 t。另外若不存在，则需要查询 ID - 1 和 ID + 1 内的桶，因为也有可能存在与 nums[i] 的差绝对值差小于等于 t 的数字，但是这两个桶内的数字若存在还需要验证是否与 nums[i] 的差的绝对值小于等于 t。只要依次检查这三个桶即可，因为其他桶内的数字肯定不符合要求。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        // 哈希表记录桶的编号和数字值
        unordered_map<int, int> hash;
        // 初始化桶大小为t+1
        long bucketSize = (long)t + 1;
        // 遍历每一个数字
        for(int i = 0; i < nums.size(); i++){
            // 计算桶序号
            int ID = getBucketID(nums[i], bucketSize);
            // 在当前桶、相邻桶中查找是否有元素，有就直接返回true
            if(hash.count(ID) 
            || (hash.count(ID-1) && min(INT_MAX-t, hash[ID-1])+t >= nums[i]) 
            || (hash.count(ID+1) && max(INT_MIN+t, hash[ID+1])-t <= nums[i])){
                return true;
            }
            // 否则把数字放到桶中
            hash[ID] = nums[i];
            // 如果当前索引大于k需要删除索引差大于k的桶
            if(i >= k){
                hash.erase(getBucketID(nums[i-k], bucketSize));
            }
        }
        return false;
    }
    // 获取桶编号
    int getBucketID(int num, long size){
        return (num >=0 ) ? num / size : (num+1) / size - 1;
    }
};

• 时间复杂度：哈希表中的查找、添加和删除操作的时间复杂度都是O（1），因此，对于一个长度为n的数组而言，它的时间复杂度是O（n）。
• 空间复杂度：哈希表的大小是k，因此，空间复杂度是O（k）。

LCR058.日程表

分析

如果需要添加的时间区间是[m, n)，就需要找出开始时间小于 m 的所有事项中开始最晚的一个（即图中时间段 2），以及开始时间大于 m 的所有事项中开始最早的一个（即图中的时间段 3）。如果待添加的时间段与这两个时间段无冲突，则可以添加入日程表中。

class MyCalendar {
public:
    map<int, int> table;
    MyCalendar() {

    }
    
    bool book(int start, int end) {
        // 找到第一个不小于 start 的元素
        auto low = table.lower_bound(start);
        
        // 检查与上一个事件是否重叠
        if (low != table.begin() && (--low)->second > start) {
            return false;
        }
        
        // 检查与下一个事件是否重叠
        low = table.lower_bound(start);
        if (low != table.end() && low->first < end) {
            return false;
        }

        // 如果不重叠，则添加到日历
        table[start] = end;
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

• 时间复杂度：O(logn)
• 空间复杂度：O(n)

总结

本章介绍了树这种数据结构，尤其着重介绍了二叉树。与二叉树相关的面试题大多与遍历相关，本章通过大量的面试题全面介绍了二叉树的中序遍历、前序遍历和后序遍历这3种深度优先搜索算法。笔者强烈建议读者对这3种遍历的循环和递归代码烂熟于心，这样在解决与二叉树相关的面试题时才能得心应手。

二叉搜索树是一种特殊的二叉树，在二叉搜索树中进行搜索、添加和删除操作的平均时间复杂度都是O（logn）。如果按照中序遍历的顺序遍历一棵二叉搜索树，那么按照从小到大的顺序依次遍历每个节点。由于这个特性，与二叉搜索树相关的很多面试题都适合使用中序遍历解决。

Java中提供的TreeSet和TreeMap（C++中为set和map）这两种数据结构实现了平衡二叉搜索树。如果需要动态地在一个排序的数据集合中添加元素，或者需要根据数据的大小查找，那么可以使用TreeSet或TreeMap解决。

[!WARNING]
题目都是用STL自带的数据结构实现的，对于二叉搜索树、二叉平衡树、红黑树等等还不熟悉，待日后补充。