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 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("测试开始") 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;}
复制代码
评论