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完整代码如下：

package mainimport (    "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("测试开始")    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("出错了!")        }    }    fmt.Println("测试结束")}

在这里插入图片描述

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!("测试开始");    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!("出错了!");        }    }    println!("测试结束");}

在这里插入图片描述

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 << "测试开始" << 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 << "出错了!" << std::endl;        }    }    std::cout << "测试结束" << 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函数的实现    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;}// 用于比较的函数int compare(const void* a, const void* b) {    return (*(int*)a - *(int*)b);}// 生成随机数组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("测试开始\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("出错了！\n");        }        free(arr);    }    printf("测试结束\n");    return 0;}

在这里插入图片描述

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。

公众号