My space-saving Java solution


  • 1
    Y

    Most solution uses two PriorityQueue, which uses a large space.
    In fact, to solve this problem, we just need a sorted array through which we can add, delete, and insert a element in a specific position which make the array is still in ascending( or descending) order. So, we can use ArrayList to define a new ADT, called SortedArray, which meets out needs. It is quite simple. Following is the code:

    class SortedArray{
            
            List<Integer> array;
            SortedArray(){
                array = new ArrayList<Integer>();
            }
           // following method could be optimized by Binary Search, whose run time is O(logn)
            void add(int val){
                int i = array.size()-1;
                while(i>=0&&array.get(i)>val) i--;
                array.add(i+1, val);
            }
            void delete(int val){
                array.remove((Integer)val);
            }
            int get(int val){
                return array.get(val);
            }
    }
    

    By using this SortedArray, we can maintain a ordered array when add, delete, or insert a value and its space use is CONSTANT. And time complexity for the solution could be optimized to O(n*logn). Here is the total solution:

    public class Solution {
        public double[] medianSlidingWindow(int[] nums, int k) {
            if(nums == null || nums.length < 1 || k < 1) return null;
            int len = nums.length, i = 0;
            double[] res = new double[len-k+1];
            SortedArray array = new SortedArray();
            while(i<len){
                if(i-k+1>0)
                    array.delete(nums[i-k]);
                array.add(nums[i++]);
                if(i-k>=0){
                    if(k % 2 == 0)
                        res[i-k] = array.get((k>>>1)-1)/2.0 + array.get(k>>>1)/2.0;
                    else
                        res[i-k] = array.get(k>>>1);
                }
            }
            return res;
            
        }
        
        class SortedArray{
            
            List<Integer> array;
            
            SortedArray(){
                array = new ArrayList<Integer>();
            }
            
            void add(int val){
                int i = array.size()-1;
                while(i>=0&&array.get(i)>val) i--;
                array.add(i+1, val);
            }
            
            void delete(int val){
                array.remove((Integer)val);
            }
            
            int get(int val){
                return array.get(val);
            }
        }
    }
    

Log in to reply
 

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