C#, O(n * log k), using List<T>.BinarySearch()


  • 0
    C

    Nothing outstanding about the below solution, just haven't seen much C# code posted, so there you go...

    C# List<T>.BinarySearch() is O(log k), so is List<T>.Remove().
    Keeping a sorted list representing moving window finding median by mid index is trivial, O(1).
    Then, moving the window by 1 to the right we remove left element, insert another one from the right: O(log k) + O(log k); and we do this (n - k) times.

    using System.Runtime.CompilerServices;
    
    
    public class Solution 
    {
        List<int> window = new List<int>();
        
        public double[] MedianSlidingWindow(int[] nums, int k) 
        {
            int n = nums.Length;
            
            double[] median = new double[n - k + 1];
    
            for (int p = 0; p < k; p++)  Insert( nums[p] );    median[0] = Median();
            
            int i = 0, j = k - 1;
            
            while (j < n -1 )
            {
                Remove( nums[i++] );   Insert( nums[++j] );    median[i] = Median();           
            }
            
            return median;
        }
        
        
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Insert(int v)
        {
            int idx = window.BinarySearch(v);   window.Insert( (idx < 0) ? ~idx : idx, v );
        }
        
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Remove(int v)
        {
            window.Remove(v);
        }
        
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        double Median()
        {
            int n = window.Count;
            
            return (n % 2 == 0) ?  ( (double)window[n/2-1] + (double)window[n/2]) / 2.0f :  (double)window[n/2];
        }
    }
    

Log in to reply
 

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