频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
Insert Delete GetRandom O(1)问题及解法
2017-10-03 14:32:00      个评论    来源:刘天的博客  
收藏   我要投稿

Insert Delete GetRandom O(1)问题及解法。问题描述:

Design a data structure that supports all following operations inaverageO(1)time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have thesame probabilityof being returned.

    示例:

    // Init an empty set.
    RandomizedSet randomSet = new RandomizedSet();
    
    // Inserts 1 to the set. Returns true as 1 was inserted successfully.
    randomSet.insert(1);
    
    // Returns false as 2 does not exist in the set.
    randomSet.remove(2);
    
    // Inserts 2 to the set, returns true. Set now contains [1,2].
    randomSet.insert(2);
    
    // getRandom should return either 1 or 2 randomly.
    randomSet.getRandom();
    
    // Removes 1 from the set, returns true. Set now contains [2].
    randomSet.remove(1);
    
    // 2 was already in the set, so return false.
    randomSet.insert(2);
    
    // Since 2 is the only number in the set, getRandom always return 2.
    randomSet.getRandom();

    问题分析:

    利用map和vector分别保留 和 value,这里有个小知识点,搞清楚这个,此题迎刃而解。

    如何在常量时间内删除数组的一个元素?在可改变原先顺序的基础上,我们可以将要数组最后一个元素覆盖到要删除的元素的位置,调用数组pop_back方法即可。

    过程详见代码:

    class RandomizedSet {
    public:
        unordered_map map;
    	vector res;
    	/** Initialize your data structure here. */
    	RandomizedSet() {
    		srand(time(NULL));
    	}
    
    	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    	bool insert(int val) {
    		if (!map.count(val))
    		{
    			map[val] = res.size();
    			res.emplace_back(val);
    			return true;
    		}
    		return false;
    	}
    
    	/** Removes a value from the set. Returns true if the set contained the specified element. */
    	bool remove(int val) {
    		if (!map.count(val)) return false;
    		int t = res.size() - 1;
    		map[res.back()] = map[val];
    		res[map[val]] = res.back();
    		res.pop_back();
    		map.erase(val);
    		return true;
    	}
    
    	/** Get a random element from the set. */
    	int getRandom() {
    		int index = rand() % map.size();
    		return res[index];
    	}
    };
    
    /**
     * 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();
     */
点击复制链接 与好友分享!回本站首页
上一篇:myeclipse没有部署项目的全部文件到tomcat的webapps目录下
下一篇:编程开发教程之kafka使用技巧
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站