随机：基础

0380. 常数时间插入、删除和获取随机元素 (opens new window)

题目

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

• insert(val)：当元素 val 不存在时，向集合中插入该项。
• remove(val)：元素 val 存在时，从集合中移除该项。
• getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

解析

本题的关键在于怎么在数组中实现 O(1) 复杂度的删除，解决方法是将数组末尾的元素移至删除位置，同时将数组末尾元素删除。

代码

class RandomizedSet {
    vector<int> elements;
    unordered_map<int, int> record;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (record.find(val) != record.end()) {
            return false;
        }
        record[val] = elements.size();
        elements.push_back(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (record.find(val) == record.end()) {
            return false;
        }
        int idx = record[val];
        record.erase(val);
        
        int lastVal = elements.back();
        elements.pop_back();

        if (idx != elements.size()) {
            elements[idx] = lastVal;
            record[lastVal] = idx;
        }
        
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return elements[rand() % elements.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();
 */

0381. O(1) 时间插入、删除和获取随机元素 - 允许重复 (opens new window)

题目

设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

注意: 允许出现重复元素。

• insert(val)：向集合中插入元素 val。
• remove(val)：当 val 存在时，从集合中移除一个 val。
• getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

解析

本题与 0380. 常数时间插入、删除和获取随机元素 的唯一区别在于这里允许出现重复元素，因此需要将 record 中的值类型改为 set，用于存储当前值的所有索引。

代码

class RandomizedCollection {
    vector<int> elements;
    unordered_map<int, unordered_set<int>> record;
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {

    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        bool contain = record.find(val) != record.end();
        if (!contain) {
            record[val] = unordered_set<int>();
        }
        record[val].insert(elements.size());
        elements.push_back(val);
        return !contain;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if (record.find(val) == record.end()) {
            return false;
        }
        int idx = *record[val].begin();
        record[val].erase(idx);
        if (record[val].empty()) {
            record.erase(val);
        }
        
        int lastVal = elements.back();
        elements.pop_back();

        if (idx != elements.size()) {
            elements[idx] = lastVal;
            record[lastVal].erase(elements.size());
            record[lastVal].insert(idx);
        }

        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return elements[rand() % elements.size()];
    }
};

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

0382. 链表随机节点 (opens new window)

题目

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶：如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

解析

蓄水池抽样算法。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode* head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int ans = -1, i = 0;
        while (node) {
            if (rand() % ++i == 0) {
                ans = node->val;
            }
            node = node->next;
        }
        return ans;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

0384. 打乱数组 (opens new window)

题目

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

解析

Fisher-Yates 洗牌算法，每次从当前位置之后所有元素（含当前位置）中随机选取一个，将其与当前位置的元素交换。

代码

class Solution {
    vector<int> nums;
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        vector<int> clone(nums);
        for (int i = 0; i < clone.size(); i ++) {
            int idx = rand() % (clone.size() - i) + i;
            swap(clone[i], clone[idx]);
        }
        return clone;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

0398. 随机数索引 (opens new window)

题目

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

解析

蓄水池抽样算法。

代码

class Solution {
    vector<int> nums;
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
    }
    
    int pick(int target) {
        int idx = -1, cnt = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] == target) {
                if (rand() % ++cnt == 0) {
                    idx = i;
                }
            }
        }
        return idx;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */