凑数使数组中位数为特定值问题

题目描述：
小M给你一个长度为n的数组，我们定义median数为该数组从小到大排序后，下标为(n-1)/2的数字。下标从0开始，(n-1)/2表示整数除法，即向下取整。现在我们已经得到了一个初始的数组，我们希望这个数组的median数是一个给定数字x。所以我们需要加入一些数到数组中从而完成我们的目标。数组中的元素可以重复，请问，最少需要加入多少个数字才能达成这个目标。

输入描述:
第一行输入两个整数n x (1 <= n <= 500, 1 <= x <= 10^5)。
接下来一行有n个正整数表示初始的数组，用空格分开，范围是[1, 10^5]。

输出描述:
输出需要加入最少的元素个数才能够使得新数组的median数成为x。

示例1：
输入
3 2
2 3 4
输出
1
说明：加入1，得到1 2 3 4，那么median数的下标为(4 - 1)/2 = 1, median数为2。加一个数字就可以了。

示例2：
3 4
1 2 3
输出
4
说明：加入4 5 6 7，得到1 2 3 4 5 6 7，median数为4。最少加4个数字。

解法1：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scaner = new Scanner(System.in);
        int n = scaner.nextInt();
        int x =  scaner.nextInt();
        ArrayList<Integer> nums = new ArrayList();
        boolean exist = false;
        for(int i=0; i<n; i++) {
            int temp = scaner.nextInt();
            nums.add(temp);
            if(temp == x) {
                exist = true;
            }
        }
        int ans = 0;
        if(!exist) { //不存在时，至少需要加一个。提前加好，为了使后面相等的情况一定存在
            nums.add(x);
            ans++;
        }
        nums.sort(Comparator.naturalOrder());
        //以下两个while都一定是以相等的方式退出循序
        while(nums.get((nums.size()-1)/2) > x) {
            nums.add(0, 1);//用最小可能的值1，或者用nums[0]，保证数组仍然有序
            ans++;
        }
        while(nums.get((nums.size()-1)/2) < x) {//前面是相等退出，所以如果前面循环执行了，后面的就不会执行
            nums.add(100000);//用最大可能的值100000，或者用nums[nums.size()-1]，保证数组仍然有序
            ans++;
        }
        //直接满足nums.get((nums.size()-1)/2) == x的话，前面两个循环就都不会走
        System.out.println(ans);
    }
}

解法二：进一步简化

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scaner = new Scanner(System.in);
        int n = scaner.nextInt();
        int x =  scaner.nextInt();
        int less = 0, greater = 0, equal = 0;//
        for(int i=0; i<n; i++) {
            int temp = scaner.nextInt();
            if(temp < x) {
                less++;
            } else if(temp == x) {
                equal++;
            } else {
                greater++;
            }
        }
        int m = (n-1)/2;
        if(m < less) {
            //m范围是[0,less-1],意味着m落在了less(比x小)队列中；
            //此时需要使equal最左边的数字（定义为E0）成为中位数，需要在E0右边增加数字
            //(可以理解为增加值x，这样equal=0的时候也适配此规则)
            //依照最少增加原则，使得增加后，E0左边的数字数和右边数字数相等即可
            //所以增加个数=E0当前左边的数字数-E0当前右边的数字数=less-(equal-1+greater)
            System.out.println(less-(equal-1+greater));
        } else if(m < less+equal) {
            //m范围是[less,less+equal-1],意味着m落在了equal(与x相等)队列中；此处不需要增加数字
            System.out.println(0);
        } else {
            //m范围是[less+equal,less+equal+greater-1],意味着m落在了greater(比x大)队列中；
            //此时需要使equal最右边的数字（定义为EL）成为中位数，需要在EL左边增加数字
            //(可以理解为增加值x，这样equal=0的时候也适配此规则)
            //依照最少增加原则，使得增加后，EL左边的数字数比右边数字数少一个即可（数组总个数为偶数时，中位数左边比右边少一个数）
            //所以增加个数=(EL当前右边的数字数-1)-E0当前左边的数字数=greater-1-(less+equal-1)
            System.out.println(greater-1-(less+equal-1));
        }
    }
}