写点什么

2022-04-23:给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合 或者 B 集合中 使得 A 集合和 B 集合不为空,并且 average(A) == aver

  • 2023-04-23
    北京
  • 本文字数:3284 字

    阅读完需:约 11 分钟

2022-04-23:给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合 或者 B 集合中使得 A 集合和 B 集合不为空,并且 average(A) == average(B)如果可以完成则返回 true,否则返回 false。注意:对于数组 arr, average(arr) 是 arr 的所有元素的和除以 arr 长度。输入: nums = [1,2,3,4,5,6,7,8]。输出: true。


答案 2022-04-23:


  1. 定义全局变量 nslr,分别表示数组长度、数组元素之和、左侧集合的元素个数和右侧集合的元素个数。

  2. 定义两个数组 lvaluesrvalues,用于存储左侧集合和右侧集合的指标值。

  3. 编写函数 splitArraySameAverage(nums []int) bool,其中 nums 是输入的整数数组。首先检查数组长度是否为 1,如果是则返回 false。

  4. 计算数组元素之和 s

  5. 创建一个长度为 n/2 的切片 larr 和一个长度为 n-len(larr) 的切片 rarr,将前半部分元素存储在 larr 中,将后半部分元素存储在 rarr 中。

  6. 调用函数 collect(larr, true) 收集左侧集合的指标值,并调用函数 collect(rarr, false) 收集右侧集合的指标值。

  7. 对右侧集合的指标值进行排序,以便进行二分查找。

  8. 遍历左侧集合的指标值,在右侧集合中查找是否存在相反数,如果存在则说明可以分割成两个具有相同平均数的子集,返回 true;否则返回 false。

  9. 编写函数 collect(arr []int, isLeft bool),其中 arr 是需要遍历的整数数组,isLeft 指示是否为左侧集合。在函数中调用递归函数 process(arr, 0, 0, 0, isLeft)

  10. 编写函数 process(arr []int, index int, sum int, num int, isLeft bool),其中 index 表示当前处理的元素下标,sum 表示当前元素之和,num 表示当前元素个数。如果 index 等于数组长度,则计算指标值并将其存储在 lvaluesrvalues 中。

  11. 对于每个元素,都有两种选择:不加入集合(包括左侧集合和右侧集合),或者加入集合并递归到下一个元素。因此,递归函数应该调用 process(arr, index+1, sum, num, isLeft)process(arr, index+1, sum+arr[index], num+1, isLeft) 这两个函数。

  12. 编写函数 contains(num int) bool,其中 num 是需要查找的元素。使用二分查找算法在 rvalues 数组中查找相应的元素。


时间复杂度:


该算法的时间复杂度主要受到递归函数 process 对数组的遍历方式和左侧集合大小的约束,以及二分查找函数 contains 的时间复杂度的影响。


process 函数中,对于每个元素都有两种选择,因此共有 种可能的组合。对于每种组合,最坏情况下需要进行一个二分查找操作,因此 process 函数的时间复杂度为


contains 函数中,二分查找的时间复杂度为


因此,该算法的总时间复杂度为


空间复杂度:


该算法的空间复杂度主要受到存储左侧集合指标值的数组 lvalues 和存储右侧集合指标值的数组 rvalues 的影响。这两个数组的长度分别为 ,因此总空间复杂度为


此外,还需要定义一些全局变量和局部变量,它们的空间占用不会随着输入规模的增加而增加,因此可以忽略。


总的来说,该算法的空间复杂度为 。由于 的取值范围较小,因此该算法的空间复杂度是可以接受的。

golang 完整代码如下:

package main
import ( "fmt" "sort")
var ( n int s int l int r int lvalues [1 << 15]int rvalues [1 << 15]int)
func splitArraySameAverage(nums []int) bool { n = len(nums) if n == 1 { return false }
s = 0 for _, num := range nums { s += num }
l = 0 r = 0
larr := make([]int, n/2) for i := 0; i < len(larr); i++ { larr[i] = nums[i] }
rarr := make([]int, n-len(larr)) for i := len(larr); i < len(nums); i++ { rarr[i-len(larr)] = nums[i] }
// 左侧 : 收集指标的时候,不能一个数也没有 collect(larr, true) // 右侧 : 收集指标的时候,不能所有数都用 collect(rarr, false)
sort.Ints(rvalues[:r]) for i := 0; i < l; i++ { // 左侧x -x if contains(-lvalues[i]) { return true } }
return false}
func collect(arr []int, isLeft bool) { process(arr, 0, 0, 0, isLeft)}
func process(arr []int, index int, sum int, num int, isLeft bool) { if index == len(arr) { if isLeft && num > 0 { lvalues[l] = s*num - n*sum l++ } if !isLeft && num != len(arr) { rvalues[r] = s*num - n*sum r++ } } else { process(arr, index+1, sum, num, isLeft) process(arr, index+1, sum+arr[index], num+1, isLeft) }}
func contains(num int) bool { left := 0 right := r - 1 for left <= right { mid := (left + right) / 2 if rvalues[mid] == num { return true } else if rvalues[mid] < num { left = mid + 1 } else { right = mid - 1 } } return false}
func main() { nums := []int{1, 2, 3, 4, 5, 6, 7, 8} if splitArraySameAverage(nums) { fmt.Println("可以分割成两个具有相同平均数的子集") } else { fmt.Println("无法分割成两个具有相同平均数的子集") }}
复制代码


rust 完整代码如下:

use std::cmp::Ordering;
static mut L_VALUES: [i32; 1 << 15] = [0; 1 << 15];static mut R_VALUES: [i32; 1 << 15] = [0; 1 << 15];static mut N: i32 = 0;static mut S: i32 = 0;static mut L: i32 = 0;static mut R: i32 = 0;
pub fn split_array_same_average(nums: Vec<i32>) -> bool { unsafe { N = nums.len() as i32; if N == 1 { return false; } S = nums.iter().sum(); L = 0; R = 0;
let mut larr = vec![0; N as usize / 2]; for i in 0..larr.len() { larr[i] = nums[i]; }
let mut rarr = vec![0; N as usize - larr.len()]; for i in larr.len()..nums.len() { rarr[i - larr.len()] = nums[i]; }
collect(&mut larr, 0, 0, 0, true); collect(&mut rarr, 0, 0, 0, false);
let mut r_values = [0; 1 << 15]; for i in 0..R { r_values[i as usize] = R_VALUES[i as usize]; } r_values.sort_unstable();
for i in 0..L { if contains(-L_VALUES[i as usize], &r_values) { return true; } } false }}
fn collect(arr: &mut [i32], index: usize, sum: i32, num: i32, is_left: bool) { unsafe { if index == arr.len() { if is_left && num > 0 { L_VALUES[L as usize] = S * num - N * sum; L += 1; } if !is_left && num != arr.len() as i32 { R_VALUES[R as usize] = S * num - N * sum; R += 1; } } else { collect(arr, index + 1, sum, num, is_left); collect(arr, index + 1, sum + arr[index], num + 1, is_left); } }}
fn contains(num: i32, r_values: &[i32]) -> bool { let mut left = 0; let mut right = r_values.len() - 1; while left <= right { let mid = (left + right) / 2; match r_values[mid].cmp(&num) { Ordering::Equal => return true, Ordering::Less => left = mid + 1, Ordering::Greater => right = mid - 1, } } false}
fn main() { let nums = vec![1, 2, 3, 4, 5, 6, 7, 8]; let result = split_array_same_average(nums); println!("{}", result);}
复制代码



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2022-04-23:给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合 或者 B 集合中 使得 A 集合和 B 集合不为空,并且 average(A) == aver_golang_福大大架构师每日一题_InfoQ写作社区