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}
// 查找 <v 最右的位置// 没有返回-1func 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<i32>, queries: Vec<i32>) -> Vec<i64> { 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<i32>, v: i32) -> i32 { 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<i64>, l: i32, r: i32) -> i64 { 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 <iostream>#include <vector>#include <algorithm>
using namespace std;
int bs(vector<int>& nums, int v) { 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<long long>& sum, int l, int r) { return l > r ? 0 : (sum[r + 1] - sum[l]);}
vector<long long> minOperations(vector<int>& nums, vector<int>& queries) { int n = nums.size(); sort(nums.begin(), nums.end());
vector<long long> sum(n + 1, 0); for (int i = 0; i < n; i++) { sum[i + 1] = sum[i] + nums[i]; }
vector<long long> ans; 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<int> nums = { 3, 1, 6, 8 }; vector<int> queries = { 1, 5 };
vector<long long> result = minOperations(nums, queries);
for (long long ans : result) { cout << ans << " "; } cout << endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
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;}
复制代码
![2023-08-28：用go语言编写。给你一个正整数数组nums, 同时给你一个长度为 m 的整数数组 queries。 第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论