2022-04-23：给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合或者 B 集合中使得

福大大架构师每日一题

发布于 2023-06-09 10:09:30

4910

发布于 2023-06-09 10:09:30

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. 定义全局变量 n、s、l 和 r，分别表示数组长度、数组元素之和、左侧集合的元素个数和右侧集合的元素个数。
2. 定义两个数组 lvalues 和 rvalues，用于存储左侧集合和右侧集合的指标值。
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 等于数组长度，则计算指标值并将其存储在 lvalues 或 rvalues 中。
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 函数中，对于每个元素都有两种选择，因此共有 2^n 种可能的组合。对于每种组合，最坏情况下需要进行一个二分查找操作，因此 process 函数的时间复杂度为 O(n\times 2^n \log n)。

在 contains 函数中，二分查找的时间复杂度为 O(\log n)。

因此，该算法的总时间复杂度为 O(n\times 2^n \log n)。

空间复杂度：

该算法的空间复杂度主要受到存储左侧集合指标值的数组 lvalues 和存储右侧集合指标值的数组 rvalues 的影响。这两个数组的长度分别为 2^{n/2} 和 2^{n-n/2}，因此总空间复杂度为 O(2^n)。

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

总的来说，该算法的空间复杂度为 O(2^n)。由于 n 的取值范围较小，因此该算法的空间复杂度是可以接受的。

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