2023-07-17：给定一个数组arr，长度为n，再给定一个数字k，表示|arr|内元素|算法|调用

2023-07-17：给定一个数组arr，长度为n，

再给定一个数字k，表示一定要将arr划分成k个集合，

每个数字只能进一个集合。

返回每个集合内部的平均值都累加起来最小的值。

平均值向下取整。

1 <= n <= 10^5，

0 <= arr[i] <= 10^5，

1 <= k <= n。

真实大厂笔试题。

答案2023-07-17：

算法1（minAverageSum1）：

1.定义一个结构体Info，包含两个字段：sum表示集合内所有元素的和，cnt表示集合内元素的个数。

2.定义函数minAverageSum1(arr []int, k int) int，接收数组arr和整数k作为参数，返回最小平均值累加和。

3.若数组arr的长度小于k，返回-1。

4.创建一个长度为k的Info类型的切片sets，用于存储k个集合的信息。

5.调用递归函数process(arr, 0, k, sets)来计算最小平均值累加和。

6.函数process(arr []int, i int, k int, sets []Info) int表示将arr数组从索引i开始的元素划分到sets集合中，返回最小平均值累加和。

7.若i等于arr的长度，表示所有元素都已经划分完毕，计算集合内元素的平均值并返回。

8.初始化最小平均值累加和ans为最大整数值。

9.取出当前元素arr[i]，遍历sets集合的每个元素。

10.将arr[i]加到sets[j]集合的sum字段上，同时增加sets[j]集合的cnt字段。

11.递归调用process(arr, i+1, k, sets)，传递更新后的sets集合。将返回结果与ans比较并更新ans。

12.回溯操作，将之前加入arr[i]的sum和cnt字段还原。

13.返回ans作为最终结果。

算法2（minAverageSum2）：

1.定义函数minAverageSum2(arr []int, k int) int，接收数组arr和整数k作为参数，返回最小平均值累加和。

2.若数组arr的长度小于k，返回-1。

3.对数组arr进行升序排序。

4.初始化ans为0，用于记录平均值累加和的结果。

5.遍历排序后的arr数组，从索引0到k-2。

6.将arr[i]累加到ans上。

7.计算剩余元素的和sum，从索引k-1到数组末尾。

8.将sum除以剩余元素个数（len(arr)-k+1），并向下取整，累加到ans上。

9.返回ans作为最终结果。

测试部分：

1.设置常量N为8、V为10000，表示测试样例的大小范围。

2.设置常量testTimes为2000，表示测试次数。

3.打印"测试开始"。

4.循环testTimes次进行测试：

•随机生成一个1到N之间的数作为数组长度n。
•使用函数randomArray(n, V)随机生成一个长度为n，元素值介于0到V之间的数组arr。
•随机生成一个1到n之间的数作为集合的个数k。
•调用minAverageSum1(arr, k)得到算法1的结果ans1。
•调用minAverageSum2(arr, k)得到算法2的结果ans2。
•若ans1与ans2不相等，打印"出错了!"。

5.打印"测试结束"。

算法1（minAverageSum1）的时间复杂度和空间复杂度如下：

•时间复杂度：这个算法的时间复杂度是指数级的，具体为O(k^n)，其中n是数组arr的长度。因为算法使用了递归来穷举所有可能的划分方式，而对于每个划分方式，需要计算集合内元素的和。因此，时间复杂度随着n的增加呈指数级增长。
•空间复杂度：这个算法的空间复杂度取决于递归调用的深度，即划分的次数。在每次递归调用时，都会创建一个Info类型的切片sets，因此空间复杂度与递归调用的深度成正比，即O(k)。此外，还需要额外的空间来存储函数参数和临时变量，因此可以忽略不计。

算法2（minAverageSum2）的时间复杂度和空间复杂度如下：

•时间复杂度：这个算法的时间复杂度是O(nlogn)，其中n是数组arr的长度。算法首先对数组arr进行排序，排序的时间复杂度为O(nlogn)。然后对排序后的数组进行遍历，遍历的时间复杂度为O(n)。因此，总体的时间复杂度为O(nlogn)。
•空间复杂度：这个算法的空间复杂度主要由排序所需的额外空间决定，即O(n)。在排序过程中，可能需要额外的空间来存储临时变量和排序结果，但这个空间复杂度可以忽略不计。因此，总体的空间复杂度为O(n)。

go完整代码如下：

packagemain
import(
"fmt"
"math"
"math/rand"
"sort"
)
typeInfostruct{
sumint
cntint
}
funcminAverageSum1(arr[]int,kint)int{
iflen(arr)return-1
}
sets:=make([]Info,k)
returnprocess(arr,0,k,sets)
}
funcprocess(arr[]int,iint,kint,sets[]Info)int{
ifi==len(arr){
ans:=0
for_,set:=rangesets{
ifset.cnt==0{
returnmath.MaxInt32
}else{
ans+=set.sum/set.cnt
}
}
returnans
}else{
ans:=math.MaxInt32
cur:=arr[i]
forj:=0;jsets[j].sum+=cur
sets[j].cnt+=1
ans=min(ans,process(arr,i+1,k,sets))
sets[j].sum-=cur
sets[j].cnt-=1
}
returnans
}
}
funcmin(a,bint)int{
ifareturna
}else{
returnb
}
}
funcminAverageSum2(arr[]int,kint)int{
iflen(arr)return-1
}
sort.Ints(arr)
ans:=0
fori:=0;ians+=arr[i]
}
sum:=0
fori:=k-1;isum+=arr[i]
}
ans+=sum/(len(arr)-k+1)
returnans
}
funcrandomArray(nint,vint)[]int{
arr:=make([]int,n)
fori:=0;iarr[i]=rand.Intn(v)
}
returnarr
}
funcmain(){
N:=8
V:=10000
testTimes:=2000
fmt.Println("测试开始")
fori:=0;in:=rand.Intn(N)+1
arr:=randomArray(n,V)
k:=rand.Intn(n)+1
ans1:=minAverageSum1(arr,k)
ans2:=minAverageSum2(arr,k)
ifans1!=ans2{
fmt.Println("出错了!")
}
}
fmt.Println("测试结束")
}

rust完整代码如下：

usestd::cmp;
#[derive(Clone)]
structInfo{
sum:i32,
cnt:i32,
}
implInfo{
fnnew(s:i32,c:i32)->Info{
Info{sum:s,cnt:c}
}
}
fnmin_average_sum1(arr:&[i32],k:usize)->i32{
ifarr.len()return-1;
}
letmutsets=vec![Info::new(0,0);k];
process(arr,0,k,&mutsets)
}
fnprocess(arr:&[i32],i:usize,k:usize,sets:&mutVec)->i32{
ifi==arr.len(){
letmutans=0;
forsetinsets{
ifset.cnt==0{
returni32::max_value();
}else{
ans+=set.sum/set.cnt;
}
}
returnans;
}else{
letmutans=i32::max_value();
letcur=arr[i];
forjin0..k{
sets[j].sum+=cur;
sets[j].cnt+=1;
ans=cmp::min(ans,process(arr,i+1,k,sets));
sets[j].sum-=cur;
sets[j].cnt-=1;
}
returnans;
}
}
fnmin_average_sum2(arr:&[i32],k:usize)->i32{
ifarr.len()return-1;
}
letmutsorted_arr=arr.to_vec();
sorted_arr.sort();
letmutans=0;
foriin0..(k-1){
ans+=sorted_arr[i];
}
letmutsum=0;
foriin(k-1)..arr.len(){
sum+=sorted_arr[i];
}
ans+=sum/(arr.len()-k+1)asi32;
ans
}
fnrandom_array(n:usize,v:i32)->Vec{
letmutans=vec![0;n];
foriin0..n{
ans[i]=rand::random::()%v;
}
ans
}
fnmain(){
constN:usize=8;
constV:i32=10000;
constTEST_TIMES:usize=2000;
println!("测试开始");
for_in0..TEST_TIMES{
letn=rand::random::()%N+1;
letarr=random_array(n,V);
letk=rand::random::()%n+1;
letans1=min_average_sum1(&arr,k);
letans2=min_average_sum2(&arr,k);
ifans1!=ans2{
println!("出错了!");
}
}
println!("测试结束");
}

c++完整代码如下：

#include
#include
#include
structInfo{
intsum;
intcnt;
Info(ints,intc):sum(s),cnt(c){}
};
intprocess(conststd::vector&arr,inti,intk,std::vector&sets){
if(i==arr.size()){
intans=0;
for(constauto&set:sets){
if(set.cnt==0){
returnINT_MAX;
}
else{
ans+=set.sum/set.cnt;
}
}
returnans;
}
else{
intans=INT_MAX;
intcur=arr[i];
for(intj=0;jsets[j].sum+=cur;
sets[j].cnt+=1;
ans=std::min(ans,process(arr,i+1,k,sets));
sets[j].sum-=cur;
sets[j].cnt-=1;
}
returnans;
}
}
intminAverageSum1(conststd::vector&arr,intk){
if(arr.size()return-1;
}
std::vectorsets(k,Info(0,0));
returnprocess(arr,0,k,sets);
}
intminAverageSum2(conststd::vector&arr,intk){
if(arr.size()return-1;
}
std::vectorsortedArr=arr;
std::sort(sortedArr.begin(),sortedArr.end());
intans=0;
for(inti=0;ians+=sortedArr[i];
}
intsum=0;
for(inti=k-1;isum+=sortedArr[i];
}
ans+=sum/(sortedArr.size()-k+1);
returnans;
}
std::vectorrandomArray(intn,intv){
std::vectorarr(n);
for(inti=0;iarr[i]=rand()%v;
}
returnarr;
}
intmain(){
intN=8;
intV=10000;
inttestTimes=2000;
std::cout<<"测试开始"<for(inti=0;iintn=rand()%N+1;
std::vectorarr=randomArray(n,V);
intk=rand()%n+1;
intans1=minAverageSum1(arr,k);
intans2=minAverageSum2(arr,k);
if(ans1!=ans2){
std::cout<<"出错了!"<}
}
std::cout<<"测试结束"<return0;
}

c完整代码如下：

#include
#include
typedefstruct{
intsum;
intcnt;
}Info;
intprocess(intarr[],intn,inti,intk,Infosets[]){
if(i==n){
intans=0;
for(intj=0;jif(sets[j].cnt==0){
returnINT_MAX;
}
else{
ans+=sets[j].sum/sets[j].cnt;
}
}
returnans;
}
else{
intans=INT_MAX;
intcur=arr[i];
for(intj=0;jsets[j].sum+=cur;
sets[j].cnt+=1;
ans=(anssets[j].sum-=cur;
sets[j].cnt-=1;
}
returnans;
}
}
intminAverageSum1(intarr[],intn,intk){
if(nreturn-1;
}
Info*sets=(Info*)malloc(k*sizeof(Info));
for(inti=0;isets[i].sum=0;
sets[i].cnt=0;
}
intresult=process(arr,n,0,k,sets);
free(sets);
returnresult;
}
intcompare(constvoid*a,constvoid*b);
intminAverageSum2(intarr[],intn,intk){
if(nreturn-1;
}
qsort(arr,n,sizeof(int),compare);//需要包含stdlib.h以及compare函数的实现
intans=0;
for(inti=0;ians+=arr[i];
}
intsum=0;
for(inti=k-1;isum+=arr[i];
}
ans+=sum/(n-k+1);
returnans;
}
//用于比较的函数
intcompare(constvoid*a,constvoid*b){
return(*(int*)a-*(int*)b);
}
//生成随机数组
int*randomArray(intn,intv){
int*arr=(int*)malloc(n*sizeof(int));
for(inti=0;iarr[i]=rand()%v;
}
returnarr;
}
intmain(){
intN=8;
intV=10000;
inttestTimes=2000;
printf("测试开始\n");
for(inti=0;iintn=rand()%N+1;
int*arr=randomArray(n,V);
intk=rand()%n+1;
intans1=minAverageSum1(arr,n,k);
intans2=minAverageSum2(arr,n,k);
if(ans1!=ans2){
printf("出错了！\n");
}
free(arr);
}
printf("测试结束\n");
return0;
}