2023-08-28：用go语言编写。给你一个正整数数组nums, 同时给你一个长度为 m 的整数数组 queries。
第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：
将数组里一个元素 增大 或者 减小 1 。请你返回一个长度为 m 的数组 answer ，
其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。
注意，每次查询后，数组变回最开始的值。
输入：nums = [3,1,6,8], queries = [1,5]。
输出：[14,10]。
来自左程云。
答案2023-08-28：
大体过程如下：
1.定义 minOperations 函数，用于计算将 nums 中的元素转换为 queries 中每个元素所需的最少操作次数。函数接受两个参数：nums（正整数数组）和 queries（整数数组）。
2.获取 nums 数组的长度，对 nums 进行排序，并创建一个长度为 n+1 的 sum 数组，用于保存从 nums 累加得到的前缀和。
3.创建一个空的 ans 数组，用于存储结果。
4.遍历 queries 中的每个元素 v。
5.在 bs 函数中，使用二分查找找到 nums 中小于 v 的最右位置，并将结果赋给 less。
6.计算当前查询对应的最少操作次数 curAns:
初始化变量 curAns 为 (less+1)*v - sum0(sum, 0, less)，表示将小于 v 的元素增加到 v 的操作次数。
在 bs 函数中，使用二分查找找到 nums 中大于等于 v+1 的最左位置，并将结果赋给 more。
将 curAns 更新为 curAns + sum0(sum, more+1, n-1) - (n-more-1)*v，表示将大于 v 的元素减小到 v 的操作次数。
7.将 curAns 添加到 ans 数组中。
8.返回得到的 ans 数组作为结果。
9.在 main 函数中，定义给定的 nums 和 queries。
10.调用 minOperations 函数，并将结果赋给 result。
11.打印结果 result。
总体的时间复杂度是 O(m*log(n))，其中 m 是 queries 的长度，n 是 nums 的长度。这是因为对于每个查询，都需要使用二分查找来找到相应的位置。
总体的空间复杂度是 O(n)，其中 n 是 nums 的长度。这是因为需要创建额外的数组 sum 来保存前缀和。
go完整代码如下：
package main
import (
"fmt"
"sort"
)
func minOperations(nums []int, queries []int) []int {
n := len(nums)
sort.Ints(nums)
sum := make([]int, n+1)
for i := 0; i < n; i++ {
sum[i+1] = sum[i] + int(nums[i])
}
ans := make([]int, 0)
var less, more, curAns int
for _, v := range queries {
less = bs(nums, v)
curAns = (less+1)*int(v) - sum0(sum, 0, int(less))
more = bs(nums, v+1)
curAns += sum0(sum, more+1, n-1) - int(n-more-1)*int(v)
ans = append(ans, curAns)
}
return ans
}
// 查找 // 没有返回-1 func bs(nums []int, v int) int { l := 0 r := len(nums) - 1 var m, ans int = -1, -1 for l <= r { m = int((l + r) / 2) if nums[m] < v { ans = m l = int(m + 1) } else { r = int(m - 1) } } return ans } func sum0(sum []int, l, r int) int { if l > r { return 0 } return sum[r+1] - sum[l] } func main() { nums := []int{3, 1, 6, 8} queries := []int{1, 5} result := minOperations(nums, queries) fmt.Println(result) } rust完整代码如下： fn min_operations(nums: Vec let mut nums = nums.clone(); nums.sort(); let n = nums.len() as i32; let mut sum = vec![0; n as usize + 1]; for i in 0..n { sum[i as usize + 1] = sum[i as usize] + nums[i as usize] as i64; } let mut ans = Vec::new(); for v in queries { let less = bs(&nums, v); let mut cur_ans = (less + 1) as i64 * v as i64 - sum0(&sum, 0, less); let more = bs(&nums, v + 1); cur_ans += sum0(&sum, more + 1, n - 1) - (n - more - 1) as i64 * v as i64; ans.push(cur_ans); } ans } fn bs(nums: &Vec let mut l = 0; let mut r = nums.len() as i32 - 1; let mut ans = -1; while l <= r { let m = (l + r) / 2; if nums[m as usize] < v { ans = m; l = m + 1; } else { r = m - 1; } } ans } fn sum0(sum: &Vec if l > r { 0 } else { sum[r as usize + 1] - sum[l as usize] } } fn main() { let nums = vec![3, 1, 6, 8]; let queries = vec![1, 5]; let result = min_operations(nums, queries); println!("{:?}", result); } c++完整代码如下： #include #include #include using namespace std; int bs(vector int l = 0; int r = nums.size() - 1; int m, ans = -1; while (l <= r) { m = (l + r) / 2; if (nums[m] < v) { ans = m; l = m + 1; } else { r = m - 1; } } return ans; } long long sum0(vector return l > r ? 0 : (sum[r + 1] - sum[l]); } vector int n = nums.size(); sort(nums.begin(), nums.end()); vector for (int i = 0; i < n; i++) { sum[i + 1] = sum[i] + nums[i]; } vector int less, more; long long curAns; for (int v : queries) { less = bs(nums, v); curAns = (long long)(less + 1) * v - sum0(sum, 0, less); more = bs(nums, v + 1); curAns += sum0(sum, more + 1, n - 1) - (long long)(n - more - 1) * v; ans.push_back(curAns); } return ans; } int main() { vector vector vector for (long long ans : result) { cout << ans << " "; } cout << endl; return 0; } c完整代码如下： #include #include int binarySearch(int* nums, int numsSize, int v) { int l = 0; int r = numsSize - 1; int m, ans = -1; while (l <= r) { m = (l + r) / 2; if (nums[m] < v) { ans = m; l = m + 1; } else { r = m - 1; } } return ans; } long long sum(long long* sumArray, int l, int r) { return l > r ? 0 : (sumArray[r + 1] - sumArray[l]); } int cmpfunc(const void* a, const void* b) { return (*(int*)a - *(int*)b); } long long* minOperations(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) { int n = numsSize; qsort(nums, n, sizeof(int), cmpfunc); long long* sumArray = (long long*)malloc((n + 1) * sizeof(long long)); sumArray[0] = 0; for (int i = 0; i < n; i++) { sumArray[i + 1] = sumArray[i] + nums[i]; } long long* ans = (long long*)malloc(queriesSize * sizeof(long long)); int less, more; long long curAns; for (int i = 0; i < queriesSize; i++) { int v = queries[i]; less = binarySearch(nums, n, v); curAns = (long long)(less + 1) * v - sum(sumArray, 0, less); more = binarySearch(nums, n, v + 1); curAns += sum(sumArray, more + 1, n - 1) - (long long)(n - more - 1) * v; ans[i] = curAns; } *returnSize = queriesSize; return ans; } int main() { int nums[] = { 3, 1, 6, 8 }; int queries[] = { 1, 5 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int queriesSize = sizeof(queries) / sizeof(queries[0]); int returnSize; long long* result = minOperations(nums, numsSize, queries, queriesSize, &returnSize); printf("Result: "); for (int i = 0; i < returnSize; i++) { printf("%lld ", result[i]); } printf("\n"); free(result); return 0; } 参考链接
发表评论