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 是的长度，n 是的长度。这是因为对于每个查询，都需要使用二分查找来找到相应的位置。
queries
nums
总体的空间复杂度是 O(n)，其中 n 是的长度。这是因为需要创建额外的数组来保存前缀盒。
nums
sum
go完整代码如下：
packagemain
import(
"fmt"
"sort"
)
funcminOperations(nums[]int,queries[]int)[]int{
n:=len(nums)
sort.Ints(nums)
sum:=make([]int,n+1)
fori:=0;isum[i+1]=sum[i]+int(nums[i])
}
ans:=make([]int,0)
varless,more,curAnsint
for_,v:=rangequeries{
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)
}
returnans
}
//查找
//没有返回-1
funcbs(nums[]int,vint)int{
l:=0
r:=len(nums)-1
varm,ansint=-1,-1
forl<=r{
m=int((l+r)/2)
ifnums[m]ans=m
l=int(m+1)
}else{
r=int(m-1)
}
}
returnans
}
funcsum0(sum[]int,l,rint)int{
ifl>r{
return0
}
returnsum[r+1]-sum[l]
}
funcmain(){
nums:=[]int{3,1,6,8}
queries:=[]int{1,5}
result:=minOperations(nums,queries)
fmt.Println(result)
}
rust完整代码如下：
fnmin_operations(nums:Vec,queries:Vec)->Vec{
letmutnums=nums.clone();
nums.sort();
letn=nums.len()asi32;
letmutsum=vec![0;nasusize+1];
foriin0..n{
sum[iasusize+1]=sum[iasusize]+nums[iasusize]asi64;
}
letmutans=Vec::new();
forvinqueries{
letless=bs(&nums,v);
letmutcur_ans=(less+1)asi64*vasi64-sum0(&sum,0,less);
letmore=bs(&nums,v+1);
cur_ans+=sum0(&sum,more+1,n-1)-(n-more-1)asi64*vasi64;
ans.push(cur_ans);
}
ans
}
fnbs(nums:&Vec,v:i32)->i32{
letmutl=0;
letmutr=nums.len()asi32-1;
letmutans=-1;
whilel<=r{
letm=(l+r)/2;
ifnums[masusize]ans=m;
l=m+1;
}else{
r=m-1;
}
}
ans
}
fnsum0(sum:&Vec,l:i32,r:i32)->i64{
ifl>r{
0
}else{
sum[rasusize+1]-sum[lasusize]
}
}
fnmain(){
letnums=vec![3,1,6,8];
letqueries=vec![1,5];
letresult=min_operations(nums,queries);
println!("{:?}",result);
}
c++完整代码如下：
#include
#include
#include
usingnamespacestd;
intbs(vector&nums,intv){
intl=0;
intr=nums.size()-1;
intm,ans=-1;
while(l<=r){
m=(l+r)/2;
if(nums[m]ans=m;
l=m+1;
}
else{
r=m-1;
}
}
returnans;
}
longlongsum0(vector&sum,intl,intr){
returnl>r?0:(sum[r+1]-sum[l]);
}
vectorminOperations(vector&nums,vector&queries){
intn=nums.size();
sort(nums.begin(),nums.end());
vectorsum(n+1,0);
for(inti=0;isum[i+1]=sum[i]+nums[i];
}
vectorans;
intless,more;
longlongcurAns;
for(intv:queries){
less=bs(nums,v);
curAns=(longlong)(less+1)*v-sum0(sum,0,less);
more=bs(nums,v+1);
curAns+=sum0(sum,more+1,n-1)-(longlong)(n-more-1)*v;
ans.push_back(curAns);
}
returnans;
}
intmain(){
vectornums={3,1,6,8};
vectorqueries={1,5};
vectorresult=minOperations(nums,queries);
for(longlongans:result){
cout<}
cout<
return0;
}
c完整代码如下：
#include
#include
intbinarySearch(int*nums,intnumsSize,intv){
intl=0;
intr=numsSize-1;
intm,ans=-1;
while(l<=r){
m=(l+r)/2;
if(nums[m]ans=m;
l=m+1;
}
else{
r=m-1;
}
}
returnans;
}
longlongsum(longlong*sumArray,intl,intr){
returnl>r?0:(sumArray[r+1]-sumArray[l]);
}
intcmpfunc(constvoid*a,constvoid*b){
return(*(int*)a-*(int*)b);
}
longlong*minOperations(int*nums,intnumsSize,int*queries,intqueriesSize,int*returnSize){
intn=numsSize;
qsort(nums,n,sizeof(int),cmpfunc);
longlong*sumArray=(longlong*)malloc((n+1)*sizeof(longlong));
sumArray[0]=0;
for(inti=0;isumArray[i+1]=sumArray[i]+nums[i];
}
longlong*ans=(longlong*)malloc(queriesSize*sizeof(longlong));
intless,more;
longlongcurAns;
for(inti=0;iintv=queries[i];
less=binarySearch(nums,n,v);
curAns=(longlong)(less+1)*v-sum(sumArray,0,less);
more=binarySearch(nums,n,v+1);
curAns+=sum(sumArray,more+1,n-1)-(longlong)(n-more-1)*v;
ans[i]=curAns;
}
*returnSize=queriesSize;
returnans;
}
intmain(){
intnums[]={3,1,6,8};
intqueries[]={1,5};
intnumsSize=sizeof(nums)/sizeof(nums[0]);
intqueriesSize=sizeof(queries)/sizeof(queries[0]);
intreturnSize;
longlong*result=minOperations(nums,numsSize,queries,queriesSize,&returnSize);
printf("Result:");
for(inti=0;iprintf("%lld",result[i]);
}
printf("\n");
free(result);
return0;
}
热门跟贴