2023-07-17：给定一个数组arr，长度为n， 再给定一个数字k，表示一定要将arr划分成k个集合， 每个数字只能进一个集

举报
福大大架构师每日一题 发表于 2023/07/17 21:08:29 2023/07/17
【摘要】 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，包...

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;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入