leetcode381. Insert Delete GetRandom O(1) - Duplic

h9911 发布于2019-08-16 15:06 / 759人阅读

摘要：题目要求设计一个数据结构，支持能够在的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。网上有一些实现采用来解决，这是不合理的。此时的代码如下

题目要求

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。

强烈建议先看一下这个问题的基础版本，传送门在这里。

思路和代码

遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和hashmap来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：
假如现在插入1,2,3,3,4,3,3
此时的map中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]
我们先执行删除1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上map应当被更新为2:[1] 3:[2,3,5,0] 4:[4]
接着我们再删除2，此时虽然最后一个元素还是3，但是这个3在位置数组中的位置却是需要O(n)的时间来查询的，这就违反了O(1)的删除时间复杂度。

网上有一些java实现采用OrderSet来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要O(lgn)的时间复杂度来完成

这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：
先插入1，则map的值为[1:[0]]，list的值为[[1,0]] 此处的0代表1这个值在下标数组[0]中位于第0个位置上。
在插入2，则map的值为[1:[0], 2:[1]], list的值为[[1,0],[2,0]]
再插入1，此时map=[1:[0, 2], 2:[1], list的值为[[1,0],[2,0],[1,1]]
此时删除2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从map中得出2最后一次在数组中出现的下标为1，我们需要将最后位置上的1替换掉当前2的值，之后我们还能从数组中得知，1这个数字它对应的位置下标的索引为2，因此我们再将map[1]中map[1][2]的值替换为2所在的新的位置，即1。此时的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]

代码如下：

public class InsertDeleteGetRandomDuplicatesallowed_381 {
    private List list;
    private Map> index;
     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public InsertDeleteGetRandomDuplicatesallowed_381() {
        list = new ArrayList<>();
        index = new HashMap<>();
    }
    public boolean insert(int val) {
        boolean contains = true;
        if(!index.containsKey(val) || index.get(val).isEmpty()) {
            contains = false;
        }
        
        List tmp = index.getOrDefault(val, new ArrayList<>());
        tmp.add(list.size());
        index.put(val, tmp);

        list.add(new Pair(val,  tmp.size()-1));
        return !contains;
        
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!index.containsKey(val) || index.get(val).isEmpty()) {
            return false;
        }
        List tmp = index.get(val);
        int position = tmp.remove(tmp.size()-1);
        if(position != list.size()-1) {
            Pair lastPair = list.get(list.size()-1);
            int lastValue = lastPair.value;            
            List lastValuePositions = index.get(lastValue);
            lastValuePositions.set(lastPair.position, position);
            list.set(position, lastPair);
        }
        list.remove(list.size()-1);
        return true;
        
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int position = (int)Math.floor((Math.random() * list.size()));
        return list.get(position).value;
    }
    
    public static class Pair{
        int value;
        int position;
        
        public Pair(int value, int position) {
            this.value = value;
            this.position = position;
        }
    }
   
}

专线服务服务器托管 on_delete oracle语句 insert GetRandom Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73269.html

Insert Delete GetRandom O(1) & Duplicates allo

摘要：思路可以实现时间复杂度的和，但是要求也是，只用是不可以的。但是在里面查找的时间复杂度依然是，可以想到用来记录对应的，这样查找的时间也是常数。用可以保持顺序，但是的时间复杂度是。 380. Insert Delete GetRandom O(1) Design a data structure that supports all following operations in aver...

2shou 2019-08-14 17:11 评论0 收藏0
leetcode380. Insert Delete GetRandom O(1)

摘要：题目要求设计一个数据结构，使得能够在的时间复杂度中插入数字，删除数字，以及随机获取一个数字。因此，使用来查询时不可避免的。如何实现的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。题目要求 Design a data structure that supports all following operations in average O(1)...

phoenixsky 2019-08-16 15:06 评论0 收藏0
Design Phone Directory

摘要：题目链接直接用一个，结果了看了加了个，不过感觉没什么必要加，反正保存的都一样，只是的时间大于，用可以保证。看了题目条件是可以随便返回一个值，但是不让这么做。很无语啊如果这道题要求要求的是的，那就和一样了。 Design Phone Directory 题目链接：https://leetcode.com/problems... 直接用一个set，结果tle了= = public clas...

NicolasHe 2019-08-14 17:26 评论0 收藏0
哈希函数与哈希表

摘要：哈希函数与哈希表一哈希函数哈希函数性质输入域是无穷的输出域有穷的当输入参数固定的情况下，返回值一定一样当输入不一样，可能得到一样的值。哈希函数与哈希表一、哈希函数 1.1 哈希函数性质： input输入域是无穷的 output输出域有穷的当输入参数固定的情况下，返回值一定一样当输入不一样，可能得到一样的值。(必然会出现，因为输入域很大，输出域很小)，产生哈希碰撞均匀分布的特...

Rainie 2019-08-19 11:04 评论0 收藏0
LeetCode[72] Edit Distance

摘要：复杂度思路考虑用二维来表示变换的情况。如果两个字符串中的字符相等，那么如果两个字符串中的字符不相等，那么考虑不同的情况表示的是，从字符串到的位置转换到字符串到的位置，所需要的最少步数。 LeetCode[72] Edit Distance Given two words word1 and word2, find the minimum number of steps require...

call_me_R 2019-08-14 15:00 评论0 收藏0