<Random> 380 381（hard） 138

380. Insert Delete GetRandom O(1)

class RandomizedSet {

    ArrayList<Integer> nums;

    HashMap<Integer, Integer> locs;

    Random rand = new Random();

    /** Initialize your data structure here. */

    public RandomizedSet() {

        nums = new ArrayList<Integer>();

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

    }

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

    public boolean insert(int val) {

        boolean contain = locs.containsKey(val);

        if( contain ) return false;

        locs.put(val, nums.size());

        nums.add(val);

        return true;

    }

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

    public boolean remove(int val) {

        boolean contain = locs.containsKey(val);

        if( !contain ) return false;

        int loc = locs.get(val);

        if(loc < nums.size() - 1){// not the last one than swap the last one with this val

            int lastOneVal = nums.get(nums.size() - 1);

            nums.set(loc, lastOneVal);

            locs.put(lastOneVal, loc);

        }

        locs.remove(val);

        nums.remove(nums.size() - 1);

        return true;

    }

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

    public int getRandom() {

        return nums.get(rand.nextInt(nums.size()));

    }

}

381. Insert Delete GetRandom O(1) - Duplicates allowed

之前那道题不能有重复数字，而这道题可以有，那么就不能像之前那道题那样建立每个数字和其坐标的映射了，但是我们可以建立数字和其所有出现位置的集合之间的映射，虽然写法略有不同，但是思路和之前那题完全一样，都是将数组最后一个位置的元素和要删除的元素交换位置，然后删掉最后一个位置上的元素。对于 insert 函数，我们将要插入的数字在 nums 中的位置加入 m[val] 数组的末尾，然后在数组 nums 末尾加入 val，我们判断是否有重复只要看 m[val] 数组只有刚加的 val 一个值还是有多个值。remove 函数是这题的难点，我们首先看 HashMap 中有没有 val，没有的话直接返回 false。然后我们取出 nums 的尾元素，把尾元素 HashMap 中的位置数组中的最后一个位置更新为 m[val] 的尾元素，这样我们就可以删掉 m[val] 的尾元素了，如果 m[val] 只有一个元素，那么我们把这个映射直接删除。然后将 nums 数组中的尾元素删除，并把尾元素赋给 val 所在的位置，注意我们在建立 HashMap 的映射的时候需要用堆而不是普通的 vector 数组，因为我们每次 remove 操作后都会移除 nums 数组的尾元素，如果我们用 vector 来保存数字的坐标，而且只移出末尾数字的话，有可能出现前面的坐标大小超过了此时 nums 的大小的情况，就会出错，所以我们用优先队列对所有的相同数字的坐标进行自动排序，每次把最大位置的坐标移出即可

class RandomizedCollection {

    List<Integer> nums;

    Map<Integer, Set<Integer>> map;

    java.util.Random random;

    /** Initialize your data structure here. */

    public RandomizedCollection() {

        nums = new ArrayList<>();

        map = new HashMap<>();

        random = new Random();

    }

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

    public boolean insert(int val) {

        boolean doesContain = map.containsKey(val);

        if(!doesContain) map.put(val, new HashSet<>());

        map.get(val).add(nums.size());

        nums.add(val);

        return !doesContain;

    }

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

    public boolean remove(int val) {

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

        if(!map.get(val).contains(nums.size() - 1)){

            int curPos = map.get(val).iterator().next();

            int lastVal = nums.get(nums.size() - 1);

            map.get(lastVal).remove(nums.size() - 1);

            map.get(lastVal).add(curPos);

            map.get(val).remove(curPos);

            map.get(val).add(nums.size() - 1);

            nums.set(curPos, lastVal);

        }

        map.get(val).remove(nums.size() - 1);

        if(map.get(val).isEmpty()) map.remove(val);

        nums.remove(nums.size() - 1);

        return true;

    }

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

    public int getRandom() {

        return nums.get(random.nextInt(nums.size()));

    }

}

138. Copy List with Random Pointer

用map<Node, Node>的形式将旧节点和新节点进行映射。

第一个循环先复制val数值，第二个循环复制next和random节点。

class Solution {

    public Node copyRandomList(Node head) {

        if(head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        Node cur = head;

        //loop 1. copy all the nodes

        while(cur != null){

           map.put(cur, new Node(cur.val, null, null));

            cur = cur.next;

        }

        //loop2. assign next ad random pointers

        cur = head;

        while(cur != null){

            map.get(cur).next = map.get(cur.next);

            map.get(cur).random = map.get(cur.random);

            cur = cur.next;

        }

        return map.get(head);

    }

}

巴特西

<Random> 380 381（hard） 138

最新文章

热门文章