双指针

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        int i = 0;
        for(int j = (n + 1) / 2; j < n; j ++ ){
            if(nums.get(i) < nums.get(j)) i ++ ;
        }

        return n - i * 2;
    }
}

二分

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        int x = nums.get(n / 2);
        int cnt = lowerBound(nums, x + 1) - lowerBound(nums, x);
        return Math.max(2 * cnt - n, n % 2);
    }

    public int lowerBound(List<Integer> nums, int x){
        int l = 0, r = nums.size();
        while(l < r){
            int mid = l + r >> 1;
            if(nums.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}