Java impl of Approach #4 "Multiset and Two Pointers" from Solution
Plain Java have no multisets, so we have to use (sorted) TreeSet, Node structure and custom comparator. Methods multiSet.lower, multiSet.higher complete with lo
Plain Java have no multisets, so we have to use (sorted) TreeSet, Node structure and custom comparator. Methods multiSet.lower, multiSet.higher complete with log(N) time complexity (worse than C++ pointers inc/dec), but "of two evils choose the least".\n\n```\n    class Node {\n        int value;\n        int count;\n\n        public Node(int value, int count) {\n            this.value = value;\n            this.count = count;\n        }\n\n        @Override\n        public boolean equals(Object o) {\n            if (this == o) return true;\n            if (o == null || getClass() != o.getClass()) return false;\n            Node node = (Node) o;\n            return value == node.value &&\n                    count == node.count;\n        }\n\n        @Override\n        public int hashCode() {\n            return Objects.hash(value, count);\n        }\n    }\n\n    final TreeSet<Node> multiSet;\n    int count = 0;\n    Node loMedian, hiMedian;\n\n    /** initialize your data structure here. */\n    public MedianFinder3() {\n        this.multiSet = new TreeSet<>((a, b) -> {\n            if (a.value == b.value)\n                return a.count - b.count;\n            else\n                return a.value - b.value;\n        });\n    }\n\n    public void addNum(int num) {\n        int size = multiSet.size();\n        Node n = new Node(num, count++);\n        multiSet.add(n);\n        if (size == 0) {\n            loMedian = n;\n            hiMedian = n;\n        } else if (size % 2 != 0) {\n            if (n.value < loMedian.value) {\n                loMedian = multiSet.lower(loMedian);\n            } else {\n                hiMedian = multiSet.higher(hiMedian);\n            }\n        } else {\n            if (n.value > loMedian.value && n.value < hiMedian.value) {\n                loMedian = multiSet.higher(loMedian);\n                hiMedian = multiSet.lower(hiMedian);\n            } else if (n.value >= hiMedian.value) {\n                loMedian = multiSet.higher(loMedian);\n            } else {\n                loMedian = hiMedian = multiSet.lower(hiMedian);\n            }\n        }\n    }\n\n    public double findMedian() {\n        if (loMedian == null && hiMedian == null)\n            return 0;\n        else if (loMedian.value == hiMedian.value)\n            return loMedian.value;\n        else\n           return (loMedian.value + hiMedian.value) * 0.5;\n    }\n```
[]