算法细节系列（30）：接口设计

找到要删除的的元素：花费O(n)

删除：
把当前位置的后续元素都向前移动一格。

这种删除比较费时，在维护有序数组时，只能用这种方法。

但此题没有必要维护有序性，所以还有一种取巧的办法，把当前元素和末尾元素进行交换，直接删除末尾元素。

删除可以在O(1)内完成，但查找却费时，所以remove操作的关键在于如何快速查找元素。

O(1)时间内完成查找的有Map,所以我们可以用一个Map来维护当前元素和它对应下标的关系。

这样在remove时可以快速定位所在下标。

public class RandomizedSet {

    List<Integer> nums;
    Map<Integer, Integer> cache;
    Random random = new Random();

    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<>();
        cache = 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 (cache.containsKey(val)) return false;
        int idx = cache.size();
        nums.add(idx,val);
        cache.put(val, idx);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the
     * specified element.
     */
    public boolean remove(int val) {
        if (!cache.containsKey(val)) return false;
        int idx = cache.get(val);
        if (idx != cache.size()-1){
            cache.put(nums.get(cache.size()-1), idx);
            nums.set(idx, nums.get(cache.size()-1));
        }
        cache.remove(val);
        nums.remove(nums.size()-1);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get(random.nextInt(cache.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        rs.insert(0);
        rs.insert(1);
        rs.remove(0);
        rs.insert(2);
        rs.remove(1);
        System.out.println(rs.getRandom());
    }
}

public class RandomizedCollection {

    List<Integer> nums;
    Map<Integer, Set<Integer>> map;
    Random random = new Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        // dup or not dup insert
        boolean dup = map.containsKey(val);
        nums.add(val);
        map.computeIfAbsent(val, a -> new LinkedHashSet<>()).add(nums.size()-1);
        return !dup;
    }

    /** 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;
        int loc = map.get(val).iterator().next();
        map.get(val).remove(loc);
        if (loc < nums.size()-1){
            int last = nums.get(nums.size()-1);
            nums.set(loc, last);
            map.get(last).remove(nums.size()-1);
            map.get(last).add(loc);
        }
        nums.remove(nums.size()-1);
        if (map.get(val).isEmpty()) map.remove(val);
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}

map:
"A": 4, "B": 4, "C": 2, "D": 1

array:
D C A B

要做到插入过程中的有序性不难，此时，假设我们有：
inc("C");
inc("C");
inc("C");
三次操作，此时C的计数值为5

array:
D C A B -> D A B C

与此同时，要让array中的C浮动到最右边，而在D和A之间，C消失了。

能够高效实现这种操作的为链表，不管是INC操作还是DEC操作，都可能改变计数值，如果把计数值当作浮动比较的val，那么链表能够很好的让结点上下浮动。且插入和删除的时间复杂度仅为O(1)。

定义：
class Bucket{
    int count;
    Set<String> keySet;
    Bucket prev;
    Bucket next;
    public Bucket(int cnt){
        count = cnt;
        keySet = new HashSet<>();
    }
}

相同计数值的key无区别，所以可以用一个keySet来装。所以：
D C A B 就可以看成 D C {A,B}，此时C的浮动将变得更简单。

count是这个结构体的唯一标识，表示计数值为count的元素集合。如：
4 = {A,B}
2 = {C}
1 = {D}

整体的设计结构如下：
head --- ValueNode1 ---- ValueNode2 ---- ... ---- ValueNodeN --- tail 
              |               |                       |               
            first           first                   first             
              |               |                       |               
           KeyNodeA        KeyNodeE                KeyNodeG           
              |               |                       |               
           KeyNodeB        KeyNodeF                KeyNodeH           
              |                                       |               
           KeyNodeC                                KeyNodeI           
              |                                                       
           KeyNodeD    

private Bucket head;
    private Bucket tail;

    private Map<String, Integer> keyCountMap;
    private Map<Integer, Bucket> countBucketMap;

    class Bucket{
        int count;
        Set<String> keySet;
        Bucket prev;
        Bucket next;
        public Bucket(int cnt){
            count = cnt;
            keySet = new HashSet<>();
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
        keyCountMap = new HashMap<>();
        countBucketMap = new HashMap<>();
    }     
 }     

countBucketMap存在的意义巨大，它相当于让双向链表成了一个快速查找的数组形式，因为countBucketMap记录了每个计数值在链表中的位置。                            

public class AllOne {

    private Bucket head;
    private Bucket tail;

    private Map<String, Integer> keyCountMap;
    private Map<Integer, Bucket> countBucketMap;

    class Bucket{
        int count;
        Set<String> keySet;
        Bucket prev;
        Bucket next;
        public Bucket(int cnt){
            count = cnt;
            keySet = new HashSet<>();
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
        keyCountMap = new HashMap<>();
        countBucketMap = new HashMap<>();
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (keyCountMap.containsKey(key)){
            changeKey(key, 1);
        }
        else{
            keyCountMap.put(key, 1);
            if (head.next.count != 1)
                addBucketAfter(new Bucket(1), head);
            head.next.keySet.add(key);
            countBucketMap.put(1, head.next);
        }
    }

    private void changeKey(String key, int step){
        int val = keyCountMap.get(key);
        keyCountMap.put(key, val + step);
        Bucket cur = countBucketMap.get(val);
        Bucket newNode;
        if (countBucketMap.containsKey(val + step)){
            newNode = countBucketMap.get(val + step);
        }else{
            newNode = new Bucket(val + step);
            countBucketMap.put(val + step, newNode);
            addBucketAfter(newNode, step == 1 ? cur : cur.prev);
        }
        newNode.keySet.add(key);
        removeKeyFromBucket(cur,key);
    }

    private void removeKeyFromBucket(Bucket cur, String key){
        cur.keySet.remove(key);
        if (cur.keySet.isEmpty()){
            countBucketMap.remove(cur.count);
            removeBucketFromList(cur);
        }
    }

    private void removeBucketFromList(Bucket bucket){
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
        bucket.next = null;
        bucket.prev = null;
    }

    private void addBucketAfter(Bucket node, Bucket head){
        head.next.prev = node;
        node.prev = head;
        node.next = head.next;
        head.next = node;
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (keyCountMap.containsKey(key)){
            int val = keyCountMap.get(key);
            if (val == 1){
                keyCountMap.remove(key);
                removeKeyFromBucket(countBucketMap.get(val), key);
            }
            else{
                changeKey(key, -1);
            }
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return tail.prev == head ? "" : (String) tail.prev.keySet.iterator().next();
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return head.next == tail ? "" : (String) head.next.keySet.iterator().next();        
    }
}

public class Twitter {

    private static int timeStamp = 0;

    Map<Integer, User> userMap; 

    private class User{
        public int id;
        public Set<Integer> followed;
        public Tweet head;

        public User(int id){
            this.id = id;
            followed = new HashSet<>();
            follow(id);
            head = null;
        }

        public void follow(int id){
            followed.add(id);
        }

        public void unfollow(int id){
            followed.remove(id);
        }

        public void postTweet(int id){
            Tweet tweet = new Tweet(id);
            tweet.next = head;
            head = tweet;
        }
    }

    private class Tweet{
        public int id;
        public int time;
        public Tweet next;
        public Tweet(int id){
            this.id = id;
            this.time = timeStamp++;
            next= null;
        }
    }

    /** Initialize your data structure here. */
    public Twitter() {
        userMap = new HashMap<Integer,User>();
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!userMap.containsKey(userId)) userMap.put(userId, new User(userId));
        userMap.get(userId).postTweet(tweetId);
    }

    /**
     * Retrieve the 10 most recent tweet ids in the user's news feed. Each item
     * in the news feed must be posted by users who the user followed or by the
     * user herself. Tweets must be ordered from most recent to least recent.
     */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> ans = new ArrayList<>();
        if (!userMap.containsKey(userId)){
            userMap.put(userId, new User(userId));
            return ans;
        }
        Set<Integer> followees = userMap.get(userId).followed;
        Queue<Tweet> queue = new PriorityQueue<>((a,b) -> b.time - a.time);
        for (int f : followees){
            User user = userMap.get(f);
            if (user.head != null)
                queue.add(user.head);
        }

        while (!queue.isEmpty() && ans.size() < 10){
            Tweet first = queue.poll();
            ans.add(first.id);
            if (first.next != null)
                queue.offer(first.next);
        }

        return ans;
    }

    /**
     * Follower follows a followee. If the operation is invalid, it should be a
     * no-op.
     */
    public void follow(int followerId, int followeeId) {
        if (!userMap.containsKey(followerId)) userMap.put(followerId, new User(followerId));
        if (!userMap.containsKey(followeeId)) userMap.put(followeeId, new User(followeeId));
        userMap.get(followerId).follow(followeeId);
    }

    /**
     * Follower unfollows a followee. If the operation is invalid, it should be
     * a no-op.
     */
    public void unfollow(int followerId, int followeeId) {
        if (followeeId == followerId) return;
        if (userMap.containsKey(followerId)){
            if (userMap.get(followerId).followed.contains(followeeId)) userMap.get(followerId).unfollow(followeeId);
        }
    }
}

public class LFUCache {

    class Node{
        public int count;
        public LinkedHashSet<Integer> keys;
        public Node next;
        public Node prev;

        public Node(int count){
            this.count = count;
            keys = new LinkedHashSet<>();
            prev = next = null;
        }
    }

    private Node head = null;
    private int cap = 0;

    Map<Integer, Integer> cache;
    Map<Integer, Node> nodeHash;
    public LFUCache(int capacity) {
        cache = new HashMap<>();
        nodeHash = new HashMap<>();
        this.cap = capacity;
    }

    private void increaseCount(int key){
        Node node = nodeHash.get(key);
        node.keys.remove(key);

        if (node.next == null){
            node.next = new Node(node.count + 1);
            node.next.prev = node;
            node.next.keys.add(key);
        }
        else if (node.next.count == node.count + 1){
            node.next.keys.add(key);
        }
        else{
            Node tmp = new Node(node.count + 1);
            tmp.keys.add(key);
            tmp.prev = node;
            tmp.next = node.next;
            node.next.prev = tmp;
            node.next = tmp;
        }

        nodeHash.put(key, node.next);
        if (node.keys.isEmpty()) remove(node);
    }

    private void addToHead(int key) {
        if (head == null){
            head = new Node(0);
            head.keys.add(key);
        }else if (head.count > 0){
            Node node = new Node(0);
            node.keys.add(key);
            node.next = head;
            head.prev = node;
            head = node;
        }else{
            head.keys.add(key);
        }
        nodeHash.put(key, head);
    }

    private void removeOld(){
        if (head == null) return;
        int old = head.keys.iterator().next();
        head.keys.remove(old);
        if (head.keys.size() == 0) remove(head);
        nodeHash.remove(old);
        cache.remove(old);
    }

    private void remove(Node node) {
        if (node.prev == null){
            head = node.next;
        }else{
            node.prev.next = node.next;
        }
        if (node.next != null){
            node.next.prev = node.prev;
        }
    }

    public int get(int key) { //update
        if (!cache.containsKey(key)) return -1;
        increaseCount(key);
        return cache.get(key);
    }

    public void put(int key, int value) { //remove
        if (cap == 0) return;
        if (cache.containsKey(key)){
            cache.put(key, value);
        }else{
            if (cache.size() < cap){
                cache.put(key, value);
            }else{
                removeOld();
                cache.put(key, value);
            }
            addToHead(key);
        }
        increaseCount(key);
    }
}

public class LRUCache {

    class Node{
        public int key;
        public Node next;
        public Node prev;

        public Node(int key){
            this.key = key;
            next = null;
            prev = null;
        }
    }

    private Node head = null;
    private Node tail = null;

    private int cap = 0;
    Map<Integer, Integer> cache;
    Map<Integer, Node> nodeMap;

    public LRUCache(int capacity) {
        cache = new HashMap<>();
        nodeMap =new HashMap<>();
        head = new Node(Integer.MAX_VALUE);
        tail = new Node(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;

        this.cap = capacity;
    }

    private void update(int key){
        Node node;
        if (nodeMap.containsKey(key)){
            node = nodeMap.get(key);
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        else{
            node = new Node(key);
        }
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
        nodeMap.put(key, node);
    }

    private void remove(){
        Node node = head.next;

        head.next = node.next;
        node.next.prev = head;

        cache.remove(node.key);
        nodeMap.remove(node.key);
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        update(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cap == 0) return;
        if (cache.containsKey(key)){
            cache.put(key, value);
        }
        else{
            if (cache.size() < cap){
                cache.put(key, value);
            }
            else{
                remove();
                cache.put(key,value);
            }
        }
        update(key);
    }
}