同时给你一个长度为 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 。
示例 2:
输入:nums = [2,9,6,3], queries = [10]
输出:[20]
解释:我们可以将数组中所有元素都增大到 10 ,总操作次数为 8 + 1 + 4 + 7 = 20 。
提示:
n == nums.length
m == queries.length
1 <= n, m <= 105
1 <= nums[i], queries[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
从几十遍地AC两数之和到现在周赛第三题磕磕绊绊独立写出来(虽然这次周赛我仍然是一名光荣的一题选手。。。),就挺感慨。
class Solution { public List<Long> minOperations(int[] nums, int[] queries) { // 存储答案 List<Long> list = new ArrayList<>(); int len = nums.length; // 存储第i个位置的前面的和(包括第i个),以及后面的和(不包括第i个)。 long[][] sum = new long[len][2]; // 排序 Arrays.sort(nums); sum[0][0] = nums[0]; // 所有小于等于第i个数字的和。 for (int i = 1; i < len; i ++) { sum[i][0] = sum[i - 1][0] + nums[i]; } // 所有大于第i个数字的和。 for (int i = len - 2; i >= 0; i --) { sum[i][1] = sum[i + 1][1] + nums[i + 1]; } for (int x : queries) { int index = search(nums, x); long res; // 如果index < 0,则说明nums中所有元素都比x大。 if (index < 0) { res = sum[len - 1][0] - (long) x * len; } else { // 结果的和即是所有比x小的数增成x,所有比x大的数减成x res = (long) x * (index + 1) - sum[index][0] + sum[index][1] - (long) x * (len - index - 1); } list.add(res); } return list; } // 二分查找,找到x在nums中的位置,如果nums中不包括x,则返回比x小的数的下标(如果所有元素都比x大,则返回-1) private int search(int[] nums, int x) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = (left + right) / 2; if (nums[mid] < x) { left = mid + 1; } else if (nums[mid] > x) { right = mid -1; } else { return mid; } } return nums[left] > x ? left - 1 : left; } }