Concise 21-Line C# by using 2 Sorted Sets


  • 4
    L
    public class MedianFinder {
        private int counter = 0;
        private SortedSet<int[]> setLow = new SortedSet<int[]>(Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        private SortedSet<int[]> setHigh = new SortedSet<int[]>(Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        public void AddNum(int num) {
            int[] newNum = new int[2]{num, counter++};
            if(setLow.Count == setHigh.Count){
                if(setLow.Count == 0 || newNum[0] <= setLow.Max[0]) setLow.Add(newNum);
                else{
                    setHigh.Add(newNum);
                    setLow.Add(setHigh.Min);
                    setHigh.Remove(setHigh.Min);
                }
            }
            else if(newNum[0] <= setLow.Max[0]){
                setLow.Add(newNum);
                setHigh.Add(setLow.Max);
                setLow.Remove(setLow.Max);
            }
            else setHigh.Add(newNum);
        }
        // return the median of current data stream
        public double FindMedian() {
            if(setLow.Count == 0) return 0;
            if(setLow.Count == setHigh.Count) return (setLow.Max[0] + setHigh.Min[0]) / 2d;
            else return setLow.Max[0];
        }
    }

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.