package question;

import java.util.*;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question480 {
 public static void main(String[] args) {
 int[] ints = {
 1, 3, -1, -3, 5, 3, 6, 7
 };
 double[] doubles = new Question480().medianSlidingWindow(ints, 3);
 for (double aDouble : doubles) {
 System.out.print(aDouble+" ");
 }
 }
 public double[] medianSlidingWindow(int[] nums, int k) {
 double[] res = new double[nums.length-k+1];
 for (int i = 0; i < res.length; i++) {
 int[] ints = Arrays.copyOfRange(nums, i, i + k);
 if (k%2==0) {
 int k1 = k/2;
 int k2 = k1+1;
 int f1 = fun(ints, 0 , k-1, k1);
 int f2 = fun(ints, 0 , k-1, k2);
 res[i]=f1/2d+f2/2d;
 } else {
 int k1 = k/2+1;
 res[i] = fun(ints, 0 , k-1, k1);
 }
 }
 return res;
 }

 private int fun(int[] nums, int left, int right, int k) {
 int m = partition(nums, left, right);
 if (nums.length-m==k) return nums[m];
 else if (nums.length-m<k) return fun(nums, left, m-1, k);
 else return fun(nums, m+1, right, k);
 }

 private int partition(int[] nums, int left, int right) {
 swap(nums, right, left + new Random().nextInt(right-left+1));
 int m = left;
 while (left<right) {
 if (nums[left]<nums[right]) {
 swap(nums, left, m++);
 }
 left++;
 }
 swap(nums, right, m);
 return m;
 }

 private void swap(int[] nums, int a, int b) {
 int t = nums[a];
 nums[a]=nums[b];
 nums[b]=t;
 }
}