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

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

时间:2023-04-23 21:25:56浏览次数:45  
标签:arr nums sum num 数组 集合

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 函数中,对于每个元素都有两种选择,因此共有 $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);
}

在这里插入图片描述

标签:arr,nums,sum,num,数组,集合
From: https://www.cnblogs.com/waitmoon/p/17347772.html

相关文章

  • 如何遍历HashMap集合?
    在Java中,HashMap是一种常用的数据结构,它提供了快速的查找、插入和删除操作。当我们需要遍历HashMap中的所有元素时,可以利用三种不同的方法实现。方法一:使用键值对遍历HashMap中存储的是键值对的形式,因此最简单的方法就是直接遍历键值对。我们可以通过以下代码实现://创建一个Ha......
  • 数组为null和数组的长度==0的区别
    //数组为null和数组的长度==0的区别int[]arr=newint[0];int[]arr1=null;//两者之间的区别在于//null是数组类型的空引用//长度为0是指一个空数组//所以,数组只要被new出来,他就不等于null,他只是长度为0而已! ......
  • 稀疏数组
    实际问题:1)基本介绍当一个数组中大部分元素都是0、或大部分都是相同的元素时,可以使用稀疏数组来保存此数组处理方法:第一行记录数组一共有几行几列,有多少个不同的值把具有不同值的元素的行、列、值,记录在一个小规模的数组中,从而缩小程序规模 2)应用实例 代码实现......
  • #yyds干货盘点# LeetCode程序员面试金典:在排序数组中查找元素的第一个和最后一个位置
    题目:给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回 [-1,-1]。你必须设计并实现时间复杂度为 O(logn) 的算法解决此问题。 示例1:输入:nums=[5,7,7,8,8,10],target=......
  • JavaScript 使用 splice 方法删除数组元素可能导致的问题
    JavaScript使用splice方法删除数组元素可能导致的问题splice()方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。JavaScript遍历数组并通过splice方法删除该数组符合某些条件的元素将会导致哪些问题?导致......
  • Leetcode 88. 合并两个有序数组 Python题解
    来源:力扣(LeetCode)链接:https://leetcode.cn/problems/merge-sorted-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。1.暴力法解题思路:由于题目要求原地合并,直接返回nums1数组。因此一个可行的方案是合并两个列表,然后对合并后的列表进行排序。用......
  • 根据数组按照时间月份分组
    {"code":200,"msg":"success","data":{"sumprice":42,"arrearslist":[{"years":2023,"month":1......
  • PHP 常用数组函数汇集,详细解释描述
    PHPArray函数函数描述PHParray()创建数组。3array_change_key_case()返回其键均为大写或小写的数组。4array_chunk()把一个数组分割为新的数组块。4array_combine()通过合并两个数组来创建一个新数组。5array_count_values()用于统计数组中所有值出现的次数。4array_diff()返回两......
  • Leetcode 53. 最大子数组和 Python题解
    来源:力扣(LeetCode)链接:https://leetcode.cn/problems/maximum-subarray著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。1.动态规划解题思路:对于当前元素nums[i]来说,最大的连续子数组可以为:nums[0:i]中的最大连续子数组加上nums[i]nums[i],此时nums[......
  • 把数组排成最小的数
    classSolution{public:staticboolcmp(inta,intb){stringas=to_string(a),bs=to_string(b);returnas+bs<bs+as;}stringprintMinNumber(vector<int>&nums){sort(nums.begin(),nums.end(),cmp);......