share my java solution using ArrayList, beats 90%


  • 0
    K
    public double[] medianSlidingWindow(int[] nums, int k) {
            double[] res=new double[nums.length-k+1];
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<k;i++){
                list.add(nums[i]);
            }
            Collections.sort(list);
            res[0]=(k%2==0)?((double)list.get(k/2-1)+(double)list.get(k/2))/2:list.get(k/2);
            for(int i=0;i<nums.length-k;i++){
                int left=nums[i];
                int right=nums[i+k];
                int index=Collections.binarySearch(list,right);
                if(index>=0) list.add(index,right);
                else list.add(-index-1,right);
                index=Collections.binarySearch(list,left);
                list.remove(index);
                res[i+1]=(k%2==0)?((double)list.get(k/2-1)+(double)list.get(k/2))/2:list.get(k/2);
            }
            return res;
    }
    

Log in to reply
 

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