Java Solution just using arrays 96%


  • 0
    S
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length - k + 1];
        int[] realNums= Arrays.copyOfRange(nums,0,k); 
        Arrays.sort(realNums);
        res[0] = findMedian(realNums);
        
        for(int i= 1;i + k <= nums.length;i++){
            //reset list remove first and add next item; keep sort state.
            //then findMedian
            replaceOne(realNums , nums[k + i - 1] , nums[i - 1]);
            res[i] = findMedian(realNums);
        }
        return res;
    }
    public double findMedian(int[] nums){
        return nums.length % 2 == 0 ? nums[nums.length / 2] / 2.0d + nums[nums.length / 2 -1] / 2.0d:nums[nums.length / 2];
    }
    /**
     * nums is a sorted array,
     * add is the new item.
     * add {add} and remove the {remove}  item.meanwhile maintain the sorted state
     */
    public void replaceOne(int[] nums, int add , int remove){
        int removeIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > add) {
                //right place to add item
                if (nums[i] == remove) {
                    //perfect place
                    nums[i] = add;
                    return;
                }
                if (removeIndex < 0) {
                    // array not ready
                    int temp = 0;
                    for (int j = i; j < nums.length; j++) {
                        temp = nums[j];
                        nums[j] = add;
                        add = temp;
                        if (add == remove) {
                            //now add has changed
                            return;
                        }
                    }
                } else {
                    //already found the removeIndex´╝Üthis means the removeIndex is lesser than i
                    System.arraycopy(nums, removeIndex + 1, nums, removeIndex, i - removeIndex -1);
                    nums[i - 1] = add;
                    return;
                }
            }
            if (nums[i] == remove) {
                removeIndex = i;
            }
        }
        if (add >= nums[nums.length - 1]) {
            System.arraycopy(nums, removeIndex + 1, nums, removeIndex, nums.length - 1 - removeIndex);
            nums[nums.length - 1] = add;
        }
    }

Log in to reply
 

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