My C# solution by SortedSet


  • 1
    S
    public class MedianFinder {
        SortedSet<Tuple<int,int>> ss1;
        SortedSet<Tuple<int,int>> ss2;
        int count = 0;
    
        /** initialize your data structure here. */
        public MedianFinder() {
            ss1 = new SortedSet<Tuple<int,int>>(Comparer<Tuple<int,int>>.Create((a,b) => 
                a.Item1 == b.Item1 ? a.Item2 - b.Item2 : a.Item1 - b.Item1
            ));
            
            ss2 = new SortedSet<Tuple<int,int>>(Comparer<Tuple<int,int>>.Create((a,b) => 
                a.Item1 == b.Item1 ? a.Item2 - b.Item2 : a.Item1 - b.Item1
            ));
        }
        
        public void AddNum(int num) 
        {
            ss2.Add(new Tuple<int,int>(num, count++));
            ss1.Add(ss2.Min);
            ss2.Remove(ss2.Min);
            if(ss1.Count > ss2.Count)
            {
                ss2.Add(ss1.Max);
                ss1.Remove(ss1.Max);
            }
        }
        
        public double FindMedian() 
        {
            if(ss1.Count == ss2.Count)
                return (double)(ss1.Max.Item1+ss2.Min.Item1)/2.0;
            else
                return ss2.Min.Item1;
        }
    }
    

Log in to reply
 

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