380. Insert Delete GetRandom O(1)

经过昨天的消沉

今天我振作了

设计个数据结构，添加，删除，随机获取都是O(1).

怎么会有这么牛逼的数据结构，所以肯定相应的要耗费空间。

添加和获取耗时O(1)是Array的特性，或者说是Map/Table的特性，思考下php的array就明白其实是index的mapping了。

Random要求O(1)那就是需要知道数据结构的大小，并且保证储存的元素是相邻的。

其实就是一个table/map，KEY是添加的元素，value是他储存在array中的位置；

然后一个array和上面的table/map对应；

再一个变量size记录总共有多少个元素，便于random.

添加，直接添加到SIZE的位置，MAP里记录，SIZE++

RANDOM，通过SIZE随便RANDOM一个数，直接从ARRAY里直接获取。

删除，为了保证所有元素在ARRAY中是相邻的，像LIST那样。用ARRAY模拟就是删除之后，后面所有的都前移，但是要求O(1)，可以把最后一个元素和它换一下。换的时候相应的改变MAP/TABLE里的信息，删除map里本来最后一个KEY（因为我们换到前面了），最后SIZE--，使得array[size]指向的位置虽然不为空，但是是标记为删除的元素，就是刚才换过来的，而RANDOM不会影响。

感觉和学习哦啊以前做过的用JAVA实现PHP ARRAY的作业有点像，只不过那个要自己写hash function

为了图省事不resize array，用了arrayList，但是意思是那个意思。。

public class RandomizedSet {

    Map<Integer,Integer> map;

    List<Integer> list;

    int size;

    /** Initialize your data structure here. */

    public RandomizedSet()

    {

        map = new HashMap<Integer,Integer>();

        list = new ArrayList<Integer>();

        this.size = 0;

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

    public boolean insert(int val)

    {

        if(map.containsKey(val)) return false;

        else

        {

            list.add(size,val);

            map.put(val,size++);

            return true;

        }

    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */

    public boolean remove(int val)

    {

        if(!map.containsKey(val)) return false;

        else if(size == 0) map.remove(val);

        else

        {

            int tailKey = list.get(size-1);

            map.put(tailKey,map.get(val));

            list.set(map.get(val),tailKey);

            size--;

            map.remove(val);

        }

        return true;

    }

    /** Get a random element from the set. */

    public int getRandom()

    {

        Random rdm = new Random();

        return list.get(rdm.nextInt(size));

    }

}

二刷。

用个Map，KEY是存的元素，VAL是元素存在arraylist里的位置。

删除是把arraylist里最后一个有效元素和删除的元素调换，同时修改map里被最后一个有效元素（key)的相应位置（value）。。

public class RandomizedSet {

    List<Integer> list;

    int num;

    Map<Integer, Integer> map;

    /** Initialize your data structure here. */

    public RandomizedSet() {

        list = new ArrayList<>();

        num = 0;

        map = new HashMap<>();

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

    public boolean insert(int val) {

        if (map.containsKey(val)) {

            return false;

        } else {

            list.add(num, val);

            map.put(val, num++);

            return true;

        }

    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */

    public boolean remove(int val) {

        if (!map.containsKey(val)) {

            return false;

        } else if (num == 0) {

            map.remove(val);

            return true;

        } else {

            int removedIndex = map.get(val);

            int backElement = list.get(num - 1);

            map.put(backElement, removedIndex);

            list.set(removedIndex, backElement);

            num--;

            map.remove(val);

            return true;

        }

    }

    /** Get a random element from the set. */

    public int getRandom() {

        Random rdm = new Random();

        return list.get(rdm.nextInt(num));

    }

}

巴特西

380. Insert Delete GetRandom O(1)

最新文章

热门文章