Skip to content

Latest commit

 

History

History
210 lines (156 loc) · 5.94 KB

设计.md

File metadata and controls

210 lines (156 loc) · 5.94 KB

设计类总结

常数时间插入、删除和获取随机元素

LeetCode中文

LeetCode英文

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

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

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

解答

使用数组vector存储元素，使用map存储键值对(数值,下标)

  1. 插入一个元素时，直接添加到vector尾部，并且将相应的键值对 (数值,下标) 插入map；
  2. 删除一个元素时，在map中查找这个元素在vector中的下标，然后将vector尾部元素和被删除的元素交换位置，然后更新map中尾元素的下标，并且删除vector尾元素，删除map中与被删除元素有关的项；
  3. 随机得到一个元素时，利用srand和rand函数实现。
  • 时间复杂度：insert，remove和getRandom都为O(1)
  • 空间复杂度：O(n)
class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        srand(time(0));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(mp.find(val) != mp.end()) return false;
        
        nums.push_back(val);
        mp[val] = nums.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(mp.find(val) == mp.end()) return false;
        
        int cur = mp[val];
        int len = nums.size();
        int last = nums[len-1];
        
        swap(nums[cur],nums[len-1]);
        
        mp[last] = cur;
        
        mp.erase(val);
        nums.pop_back();
        
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        return nums[rand() % nums.size()];
    }
    
private:
    vector<int> nums;
    unordered_map<int,int> mp;
};

/**
 * 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();
 */

LRU缓存机制

LeetCode中文

LeetCode英文

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解答

  • 时间复杂度：get和put都为O(1)
  • 空间复杂度：O(n)
class LRUCache {
public:
    LRUCache(int capacity) {
        sz = capacity;
    }
    
    int get(int key) {
        auto it = mp.find(key);
        if(it == mp.end())
        {
            return -1;
        }
        else{
            auto it1 = mp[key];
            auto tmp = *it1;
            lt.erase(it1);
            lt.push_front(tmp);
            mp[key] = lt.begin();
            return tmp.second;
        }
    }
    
    void put(int key, int value) {
        auto it = mp.find(key);
        if(it == mp.end())
        {
            if(lt.size() == sz)
            {
                mp.erase(lt.back().first);
                lt.pop_back();
            }
                
            
            lt.push_front(make_pair(key,value));
            mp.insert(make_pair(key,lt.begin()));
            
        }
        else{
            auto iter = mp[key];
            lt.erase(iter);
            mp.erase(key);
            
            lt.push_front(make_pair(key,value));
            mp.insert(make_pair(key,lt.begin()));
        }
    }
    
private:
    unordered_map<int,list<pair<int,int>>::iterator> mp;
    list<pair<int,int>> lt;
    int sz;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */