2023-07-17：給定一個(gè)數(shù)組arr，長(zhǎng)度為n，

再給定一個(gè)數(shù)字k，表示一定要將arr劃分成k個(gè)集合，

每個(gè)數(shù)字只能進(jìn)一個(gè)集合。

返回每個(gè)集合內(nèi)部的平均值都累加起來最小的值。

平均值向下取整。

1 <= n <= 10^5，

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

1 <= k <= n。

真實(shí)大廠筆試題。

答案2023-07-17：

算法1（minAverageSum1）：

1.定義一個(gè)結(jié)構(gòu)體Info，包含兩個(gè)字段：sum表示集合內(nèi)所有元素的和，cnt表示集合內(nèi)元素的個(gè)數(shù)。

2.定義函數(shù)minAverageSum1(arr []int, k int) int，接收數(shù)組arr和整數(shù)k作為參數(shù)，返回最小平均值累加和。

3.若數(shù)組arr的長(zhǎng)度小于k，返回-1。

4.創(chuàng)建一個(gè)長(zhǎng)度為k的Info類型的切片sets，用于存儲(chǔ)k個(gè)集合的信息。

5.調(diào)用遞歸函數(shù)process(arr, 0, k, sets)來計(jì)算最小平均值累加和。

6.函數(shù)process(arr []int, i int, k int, sets []Info) int表示將arr數(shù)組從索引i開始的元素劃分到sets集合中，返回最小平均值累加和。

7.若i等于arr的長(zhǎng)度，表示所有元素都已經(jīng)劃分完畢，計(jì)算集合內(nèi)元素的平均值并返回。

8.初始化最小平均值累加和ans為最大整數(shù)值。

9.取出當(dāng)前元素arr[i]，遍歷sets集合的每個(gè)元素。

10.將arr[i]加到sets[j]集合的sum字段上，同時(shí)增加sets[j]集合的cnt字段。

11.遞歸調(diào)用process(arr, i+1, k, sets)，傳遞更新后的sets集合。將返回結(jié)果與ans比較并更新ans。

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

13.返回ans作為最終結(jié)果。

算法2（minAverageSum2）：

1.定義函數(shù)minAverageSum2(arr []int, k int) int，接收數(shù)組arr和整數(shù)k作為參數(shù)，返回最小平均值累加和。

2.若數(shù)組arr的長(zhǎng)度小于k，返回-1。

3.對(duì)數(shù)組arr進(jìn)行升序排序。

4.初始化ans為0，用于記錄平均值累加和的結(jié)果。

5.遍歷排序后的arr數(shù)組，從索引0到k-2。

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

7.計(jì)算剩余元素的和sum，從索引k-1到數(shù)組末尾。

8.將sum除以剩余元素個(gè)數(shù)（len(arr)-k+1），并向下取整，累加到ans上。

9.返回ans作為最終結(jié)果。

測(cè)試部分：

1.設(shè)置常量N為8、V為10000，表示測(cè)試樣例的大小范圍。

2.設(shè)置常量testTimes為2000，表示測(cè)試次數(shù)。

3.打印"測(cè)試開始"。

4.循環(huán)testTimes次進(jìn)行測(cè)試：

• ??隨機(jī)生成一個(gè)1到N之間的數(shù)作為數(shù)組長(zhǎng)度n。

• ??使用函數(shù)randomArray(n, V)隨機(jī)生成一個(gè)長(zhǎng)度為n，元素值介于0到V之間的數(shù)組arr。

• ??隨機(jī)生成一個(gè)1到n之間的數(shù)作為集合的個(gè)數(shù)k。

• ??調(diào)用minAverageSum1(arr, k)得到算法1的結(jié)果ans1。

• ??調(diào)用minAverageSum2(arr, k)得到算法2的結(jié)果ans2。

• ??若ans1與ans2不相等，打印"出錯(cuò)了!"。

5.打印"測(cè)試結(jié)束"。

算法1（minAverageSum1）的時(shí)間復(fù)雜度和空間復(fù)雜度如下：

• ??時(shí)間復(fù)雜度：這個(gè)算法的時(shí)間復(fù)雜度是指數(shù)級(jí)的，具體為O(k^n)，其中n是數(shù)組arr的長(zhǎng)度。因?yàn)樗惴ㄊ褂昧诉f歸來窮舉所有可能的劃分方式，而對(duì)于每個(gè)劃分方式，需要計(jì)算集合內(nèi)元素的和。因此，時(shí)間復(fù)雜度隨著n的增加呈指數(shù)級(jí)增長(zhǎng)。

• ??空間復(fù)雜度：這個(gè)算法的空間復(fù)雜度取決于遞歸調(diào)用的深度，即劃分的次數(shù)。在每次遞歸調(diào)用時(shí)，都會(huì)創(chuàng)建一個(gè)Info類型的切片sets，因此空間復(fù)雜度與遞歸調(diào)用的深度成正比，即O(k)。此外，還需要額外的空間來存儲(chǔ)函數(shù)參數(shù)和臨時(shí)變量，因此可以忽略不計(jì)。

算法2（minAverageSum2）的時(shí)間復(fù)雜度和空間復(fù)雜度如下：

• ??時(shí)間復(fù)雜度：這個(gè)算法的時(shí)間復(fù)雜度是O(nlogn)，其中n是數(shù)組arr的長(zhǎng)度。算法首先對(duì)數(shù)組arr進(jìn)行排序，排序的時(shí)間復(fù)雜度為O(nlogn)。然后對(duì)排序后的數(shù)組進(jìn)行遍歷，遍歷的時(shí)間復(fù)雜度為O(n)。因此，總體的時(shí)間復(fù)雜度為O(nlogn)。

• ??空間復(fù)雜度：這個(gè)算法的空間復(fù)雜度主要由排序所需的額外空間決定，即O(n)。在排序過程中，可能需要額外的空間來存儲(chǔ)臨時(shí)變量和排序結(jié)果，但這個(gè)空間復(fù)雜度可以忽略不計(jì)。因此，總體的空間復(fù)雜度為O(n)。

go完整代碼如下：

package?main

import?(
????"fmt"
????"math"
????"math/rand"
????"sort"
)

type?Info?struct?{
????sum?int
????cnt?int
}

func?minAverageSum1(arr?[]int,?k?int)?int?{
????if?len(arr)?<?k?{
????????return?-1
????}
????sets?:=?make([]Info,?k)
????return?process(arr,?0,?k,?sets)
}

func?process(arr?[]int,?i?int,?k?int,?sets?[]Info)?int?{
????if?i?==?len(arr)?{
????????ans?:=?0
????????for?_,?set?:=?range?sets?{
????????????if?set.cnt?==?0?{
????????????????return?math.MaxInt32
????????????}?else?{
????????????????ans?+=?set.sum?/?set.cnt
????????????}
????????}
????????return?ans
????}?else?{
????????ans?:=?math.MaxInt32
????????cur?:=?arr[i]
????????for?j?:=?0;?j?<?k;?j++?{
????????????sets[j].sum?+=?cur
????????????sets[j].cnt?+=?1
????????????ans?=?min(ans,?process(arr,?i+1,?k,?sets))
????????????sets[j].sum?-=?cur
????????????sets[j].cnt?-=?1
????????}
????????return?ans
????}
}

func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}?else?{
????????return?b
????}
}

func?minAverageSum2(arr?[]int,?k?int)?int?{
????if?len(arr)?<?k?{
????????return?-1
????}
????sort.Ints(arr)
????ans?:=?0
????for?i?:=?0;?i?<?k-1;?i++?{
????????ans?+=?arr[i]
????}
????sum?:=?0
????for?i?:=?k?-?1;?i?<?len(arr);?i++?{
????????sum?+=?arr[i]
????}
????ans?+=?sum?/?(len(arr)?-?k?+?1)
????return?ans
}

func?randomArray(n?int,?v?int)?[]int?{
????arr?:=?make([]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????arr[i]?=?rand.Intn(v)
????}
????return?arr
}

func?main()?{
????N?:=?8
????V?:=?10000
????testTimes?:=?2000
????fmt.Println("測(cè)試開始")
????for?i?:=?0;?i?<?testTimes;?i++?{
????????n?:=?rand.Intn(N)?+?1
????????arr?:=?randomArray(n,?V)
????????k?:=?rand.Intn(n)?+?1
????????ans1?:=?minAverageSum1(arr,?k)
????????ans2?:=?minAverageSum2(arr,?k)
????????if?ans1?!=?ans2?{
????????????fmt.Println("出錯(cuò)了!")
????????}
????}
????fmt.Println("測(cè)試結(jié)束")
}


rust完整代碼如下：

use?std::cmp;
#[derive(Clone)]
struct?Info?{
????sum:?i32,
????cnt:?i32,
}

impl?Info?{
????fn?new(s:?i32,?c:?i32)?->?Info?{
????????Info?{?sum:?s,?cnt:?c?}
????}
}

fn?min_average_sum1(arr:?&[i32],?k:?usize)?->?i32?{
????if?arr.len()?<?k?{
????????return?-1;
????}

????let?mut?sets?=?vec![Info::new(0,?0);?k];
????process(arr,?0,?k,?&mut?sets)
}

fn?process(arr:?&[i32],?i:?usize,?k:?usize,?sets:?&mut?Vec<Info>)?->?i32?{
????if?i?==?arr.len()?{
????????let?mut?ans?=?0;
????????for?set?in?sets?{
????????????if?set.cnt?==?0?{
????????????????return?i32::max_value();
????????????}?else?{
????????????????ans?+=?set.sum?/?set.cnt;
????????????}
????????}
????????return?ans;
????}?else?{
????????let?mut?ans?=?i32::max_value();
????????let?cur?=?arr[i];
????????for?j?in?0..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;
????????}
????????return?ans;
????}
}

fn?min_average_sum2(arr:?&[i32],?k:?usize)?->?i32?{
????if?arr.len()?<?k?{
????????return?-1;
????}

????let?mut?sorted_arr?=?arr.to_vec();
????sorted_arr.sort();

????let?mut?ans?=?0;
????for?i?in?0..(k?-?1)?{
????????ans?+=?sorted_arr[i];
????}

????let?mut?sum?=?0;
????for?i?in?(k?-?1)..arr.len()?{
????????sum?+=?sorted_arr[i];
????}

????ans?+=?sum?/?(arr.len()?-?k?+?1)?as?i32;
????ans
}

fn?random_array(n:?usize,?v:?i32)?->?Vec<i32>?{
????let?mut?ans?=?vec![0;?n];
????for?i?in?0..n?{
????????ans[i]?=?rand::random::<i32>()?%?v;
????}
????ans
}

fn?main()?{
????const?N:?usize?=?8;
????const?V:?i32?=?10000;
????const?TEST_TIMES:?usize?=?2000;
????println!("測(cè)試開始");
????for?_?in?0..TEST_TIMES?{
????????let?n?=?rand::random::<usize>()?%?N?+?1;
????????let?arr?=?random_array(n,?V);
????????let?k?=?rand::random::<usize>()?%?n?+?1;
????????let?ans1?=?min_average_sum1(&arr,?k);
????????let?ans2?=?min_average_sum2(&arr,?k);
????????if?ans1?!=?ans2?{
????????????println!("出錯(cuò)了!");
????????}
????}
????println!("測(cè)試結(jié)束");
}


c++完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<algorithm>

struct?Info?{
????int?sum;
????int?cnt;

????Info(int?s,?int?c)?:?sum(s),?cnt(c)?{}
};

int?process(const?std::vector<int>&?arr,?int?i,?int?k,?std::vector<Info>&?sets)?{
????if?(i?==?arr.size())?{
????????int?ans?=?0;
????????for?(const?auto&?set?:?sets)?{
????????????if?(set.cnt?==?0)?{
????????????????return?INT_MAX;
????????????}
????????????else?{
????????????????ans?+=?set.sum?/?set.cnt;
????????????}
????????}
????????return?ans;
????}
????else?{
????????int?ans?=?INT_MAX;
????????int?cur?=?arr[i];
????????for?(int?j?=?0;?j?<?k;?j++)?{
????????????sets[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;
????????}
????????return?ans;
????}
}

int?minAverageSum1(const?std::vector<int>&?arr,?int?k)?{
????if?(arr.size()?<?k)?{
????????return?-1;
????}
????std::vector<Info>?sets(k,?Info(0,?0));
????return?process(arr,?0,?k,?sets);
}

int?minAverageSum2(const?std::vector<int>&?arr,?int?k)?{
????if?(arr.size()?<?k)?{
????????return?-1;
????}
????std::vector<int>?sortedArr?=?arr;
????std::sort(sortedArr.begin(),?sortedArr.end());
????int?ans?=?0;
????for?(int?i?=?0;?i?<?k?-?1;?i++)?{
????????ans?+=?sortedArr[i];
????}
????int?sum?=?0;
????for?(int?i?=?k?-?1;?i?<?sortedArr.size();?i++)?{
????????sum?+=?sortedArr[i];
????}
????ans?+=?sum?/?(sortedArr.size()?-?k?+?1);
????return?ans;
}

std::vector<int>?randomArray(int?n,?int?v)?{
????std::vector<int>?arr(n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????arr[i]?=?rand()?%?v;
????}
????return?arr;
}

int?main()?{
????int?N?=?8;
????int?V?=?10000;
????int?testTimes?=?2000;
????std::cout?<<?"測(cè)試開始"?<<?std::endl;
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N?+?1;
????????std::vector<int>?arr?=?randomArray(n,?V);
????????int?k?=?rand()?%?n?+?1;
????????int?ans1?=?minAverageSum1(arr,?k);
????????int?ans2?=?minAverageSum2(arr,?k);
????????if?(ans1?!=?ans2)?{
????????????std::cout?<<?"出錯(cuò)了!"?<<?std::endl;
????????}
????}
????std::cout?<<?"測(cè)試結(jié)束"?<<?std::endl;
????return?0;
}

c完整代碼如下：

#include?<stdio.h>
#include?<stdlib.h>

typedef?struct?{
????int?sum;
????int?cnt;
}?Info;

int?process(int?arr[],?int?n,?int?i,?int?k,?Info?sets[])?{
????if?(i?==?n)?{
????????int?ans?=?0;
????????for?(int?j?=?0;?j?<?k;?j++)?{
????????????if?(sets[j].cnt?==?0)?{
????????????????return?INT_MAX;
????????????}
????????????else?{
????????????????ans?+=?sets[j].sum?/?sets[j].cnt;
????????????}
????????}
????????return?ans;
????}
????else?{
????????int?ans?=?INT_MAX;
????????int?cur?=?arr[i];
????????for?(int?j?=?0;?j?<?k;?j++)?{
????????????sets[j].sum?+=?cur;
????????????sets[j].cnt?+=?1;
????????????ans?=?(ans?<?process(arr,?n,?i?+?1,?k,?sets))???ans?:?process(arr,?n,?i?+?1,?k,?sets);
????????????sets[j].sum?-=?cur;
????????????sets[j].cnt?-=?1;
????????}
????????return?ans;
????}
}

int?minAverageSum1(int?arr[],?int?n,?int?k)?{
????if?(n?<?k)?{
????????return?-1;
????}
????Info*?sets?=?(Info*)malloc(k?*?sizeof(Info));
????for?(int?i?=?0;?i?<?k;?i++)?{
????????sets[i].sum?=?0;
????????sets[i].cnt?=?0;
????}
????int?result?=?process(arr,?n,?0,?k,?sets);
????free(sets);
????return?result;
}

int?compare(const?void*?a,?const?void*?b);

int?minAverageSum2(int?arr[],?int?n,?int?k)?{
????if?(n?<?k)?{
????????return?-1;
????}
????qsort(arr,?n,?sizeof(int),?compare);?//?需要包含stdlib.h以及compare函數(shù)的實(shí)現(xiàn)
????int?ans?=?0;
????for?(int?i?=?0;?i?<?k?-?1;?i++)?{
????????ans?+=?arr[i];
????}
????int?sum?=?0;
????for?(int?i?=?k?-?1;?i?<?n;?i++)?{
????????sum?+=?arr[i];
????}
????ans?+=?sum?/?(n?-?k?+?1);
????return?ans;
}

//?用于比較的函數(shù)
int?compare(const?void*?a,?const?void*?b)?{
????return?(*(int*)a?-?*(int*)b);
}

//?生成隨機(jī)數(shù)組
int*?randomArray(int?n,?int?v)?{
????int*?arr?=?(int*)malloc(n?*?sizeof(int));
????for?(int?i?=?0;?i?<?n;?i++)?{
????????arr[i]?=?rand()?%?v;
????}
????return?arr;
}

int?main()?{
????int?N?=?8;
????int?V?=?10000;
????int?testTimes?=?2000;
????printf("測(cè)試開始\n");
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N?+?1;
????????int*?arr?=?randomArray(n,?V);
????????int?k?=?rand()?%?n?+?1;
????????int?ans1?=?minAverageSum1(arr,?n,?k);
????????int?ans2?=?minAverageSum2(arr,?n,?k);
????????if?(ans1?!=?ans2)?{
????????????printf("出錯(cuò)了！\n");
????????}
????????free(arr);
????}
????printf("測(cè)試結(jié)束\n");

????return?0;
}