package com.company;

import java.util.*;

// https://discuss.leetcode.com/topic/68736/java-just-like-meeting-point-problem

// 以上是整体解法,获得中位数中位数就可以获得结果 (just like meeting point problem)

// https://discuss.leetcode.com/topic/68758/java-o-n-time-using-quickselect/2

// 以上解法是 O(n) 获得中位数的方法 (其实是获得第K位结果的方法, Quick-select)

class Solution {

    // 对应上面的第一种方法

    public int minMoves2_old(int[] nums) {

        Arrays.sort(nums);

        int i = , j = nums.length - ;

        int ret = ;

        while (i < j) {

            ret += nums[j] - nums[i];

            i++;

            j--;

        }

        return ret;

    }

    // 对应上面的第二种方法

    public int minMoves2(int[] nums) {

        int mid = getPos(nums, nums.length/+, , nums.length-);

        int ret = ;

        for (int i=; i<nums.length; i++) {

            ret += Math.abs(nums[i]-mid);

        }

        return ret;

    }

    private int getPos(int[] nums, int k, int start, int end) {

        int pivot = nums[end];

        int left = start;

        int right = end;

        while (left <= right) {

            while (left <= right && nums[left] < pivot) left++;

            while (left <= right && nums[right] >= pivot) right--;

            if (left > right) {

                break;

            }

            swap(nums, left, right);

        }

        swap(nums, left, end);

        if (k == left+) {

            return nums[left];

        }

        if (k < left+) {

            return getPos(nums, k, start, left-);

        }

        else {

            return getPos(nums, k, left+, end);

        }

    }

    private void swap(int[] nums, int a, int b) {

        int tmp = nums[a];

        nums[a] = nums[b];

        nums[b] = tmp;

    }

}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");

        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:

        int[] nums = {,,};

        int ret = solution.minMoves2(nums);

        System.out.printf("ret:%d\n", ret);

        System.out.println();

    }

}