class Solution {
public:
vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
}
};
2602. 使数组元素全部相等的最少操作次数
给你一个正整数数组 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 。
示例 2：
输入：nums = [2,9,6,3], queries = [10] 输出：[20] 解释：我们可以将数组中所有元素都增大到 10 ，总操作次数为 8 + 1 + 4 + 7 = 20 。
提示：
n == nums.lengthm == queries.length1 <= n, m <= 1051 <= nums[i], queries[i] <= 109原站题解
golang 解法, 执行用时: 192 ms, 内存消耗: 9.6 MB, 提交时间: 2023-03-29 15:01:00
func minOperations(nums, queries []int) []int64 {
n := len(nums)
sort.Ints(nums)
sum := make([]int, n+1) // 前缀和
for i, x := range nums {
sum[i+1] = sum[i] + x
}
ans := make([]int64, len(queries))
for i, q := range queries {
j := sort.SearchInts(nums, q)
left := q*j - sum[j] // 蓝色面积
right := sum[n] - sum[j] - q*(n-j) // 绿色面积
ans[i] = int64(left + right)
}
return ans
}
java 解法, 执行用时: 59 ms, 内存消耗: 57.6 MB, 提交时间: 2023-03-29 15:00:46
class Solution {
public List<Long> minOperations(int[] nums, int[] queries) {
Arrays.sort(nums);
int n = nums.length;
var sum = new long[n + 1]; // 前缀和
for (int i = 0; i < n; ++i)
sum[i + 1] = sum[i] + nums[i];
var ans = new ArrayList<Long>(queries.length);
for (int q : queries) {
int j = lowerBound(nums, q);
long left = (long) q * j - sum[j]; // 蓝色面积
long right = sum[n] - sum[j] - (long) q * (n - j); // 绿色面积
ans.add(left + right);
}
return ans;
}
// 见 https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(int[] nums, int target) {
int left = -1, right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right;
}
}
python3 解法, 执行用时: 432 ms, 内存消耗: 45.4 MB, 提交时间: 2023-03-29 15:00:33
# 排序 + 前缀和 + 二分查找
class Solution:
def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
nums.sort()
s = list(accumulate(nums, initial=0)) # 前缀和
ans = []
for q in queries:
j = bisect_left(nums, q)
left = q * j - s[j] # 蓝色面积
right = s[n] - s[j] - q * (n - j) # 绿色面积
ans.append(left + right)
return ans