题目

给你一个正整数数组 nums 。

同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：将数组里一个元素 增大 或者 减小 1 。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

注意，每次查询后，数组变回最开始的值。

示例 1：

输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：
- 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
- 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
- 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
第一个查询的总操作次数为 2 + 5 + 7 = 14 。
第二个查询，我们可以执行以下操作：
- 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
- 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
- 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
- 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。

思想：

二分查找+ 前缀和

代码：

class Solution {
    public List<Long> minOperations(int[] nums, int[] queries) {
        // 先给数组排序
        Arrays.sort(nums);
        int n = nums.length;

        // 定义前缀和数组
        long[] preSum = new long[n+1];

        
        // 遍历数组 计算数组前缀和
        for(int i = 0; i < n; i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 用于存储每个查询的结果 queries数组中有几个值就返回几个结果
        ArrayList<Long> ans = new ArrayList<>(queries.length);
        // 遍历查询数组
        for(int q : queries){
            // 使用二分查找找到nums中第一个大于等于q 的索引
            int j = lowerBound(nums,q);
            // 将nums中所有小于q的值变为q 需要操作的次数
            long left = (long) q * j - preSum[j];
           

            // 计算大于q的所有元素变为q所需要的操作次数
            long right = preSum[n] - preSum[j] - (long) q * (n-j);
            ans.add(left + right);
        }
        return ans;

    }
    // 用于找到数组中第一个大于或等于target的第一个元素的索引
    public int lowerBound(int[] nums, int target){
        int left = -1;
        int right = nums.length;
        while(left+1 < right){
            int mid = left + (right - left) /2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
        return right;
    }
}