Derolol Blog

leetcode380 O(1) 时间插入、删除和获取随机元素

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

题解

STL 关联式容器中： set 和 map 的底层数据结构为红黑树，因为 map 和 set 要求是自动排序的，红黑树能够实现这一功能，并且各个操作的时间复杂度都较低，而 unordered_set 和 unordered_map 的底层数据结构为哈希表，查找时间复杂度为常数级

class RandomizedSet {
public:
    vector<int> data;
    unordered_map<int, int> record;

    RandomizedSet() {

    }

    bool insert(int val) {
        if (record.contains(val)) {
            return false;
        }
        data.push_back(val);
        record[val] = data.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (! record.contains(val)) {
            return false;
        }
        data[record[val]] = data[data.size() - 1];
        record[data[record[val]]] = record[val];
        data.pop_back();
        record.erase(val);
        return true;
    }

    int getRandom() {
        return data[rand() % data.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

leetcode128 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题解

• unordered_set 去重
• 遍历找到各个连续子序列的头

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for (auto n : nums) num_set.insert(n);
        int max_len = 0;
        for (auto n : num_set) {
            if (!num_set.count(n - 1)) {
                int cur_num = n;
                while (num_set.count(cur_num + 1)) {
                    cur_num ++;
                }
                max_len = max(cur_num - n + 1, max_len);
            }
        }
        return max_len;
    }
};