LeetCode_位运算_困难_805.数组的均值分割

快来打我* 2023-10-07 21:08 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回 true ， 否则返回 false。

注意：对于数组 arr , average(arr) 是 arr 的所有元素除以 arr 长度的和。

**示例 1：**  
输入: nums = \[1,2,3,4,5,6,7,8\]  
输出: true  
解释: 我们可以将数组分割为 \[1,4,5,8\] 和 \[2,3,6,7\], 他们的平均值都是4.5。

**示例 2：**  
输入: nums = \[3,1\]  
输出: false

**提示：**  
1 <= nums.length <= 30  
0 <= nums\[i\] <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/split-array-with-same-average

## 2.思路 ##

（1）位运算 & 折半枚举  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————位运算 & 折半枚举
    class Solution {
        
        public boolean splitArraySameAverage(int[] nums) {
        
            int length = nums.length;
            if (length == 1) {
        
                return false;
            }
            int m = length / 2;
            // sum 为数组 nums 中的所有元素之和
            int sum = 0;
            for (int num : nums) {
        
                sum += num;
            }
            /*
                此处如果直接将 nums 中的每个元素都减去平均值 sum / length，那么可能会引入浮点数，这样
                可能会产生误差，所以此处先将 nums 中的每个元素都先乘以 length，这样 nums 的平均值就变
                为 sum，而 nums[i] * length - sum 一定为整数，这样就避免了误差
            */
            for (int i = 0; i < length; i++) {
        
                nums[i] = nums[i] * length - sum;
            }
            //将 nums 一分为二，从前半个数组中的 m 个元素中取出若干个元素形成不同的子集，共有 2^m 种取法，每种取法得到的子数组和用 leftSet 记录
            Set<Integer> leftSet = new HashSet<>();
            for (int i = 1; i < (1 << m); i++) {
        
                int total = 0;
                //对每种取法，都要遍历前半个数组，选取相应的元素进行求和
                for (int j = 0; j < m; j++) {
        
                    if ((i & (1 << j)) != 0) {
        
                        total += nums[j];
                    }
                }
                //如果前半个数组中有部分元素之和为 0，则剩余的所有元素之和也一定为 0，此时直接返回 true 即可
                if (total == 0) {
        
                    return true;
                }
                leftSet.add(total);
            }
            // rigthSum 用于记录后半个数组的元素之和
            int rigthSum = 0;
            for (int i = m; i < length; i++) {
        
                rigthSum += nums[i];
            }
            //对后半个数组的做法与前面类似
            for (int i = 1; i < (1 << (length - m)); i++) {
        
                int total = 0;
                for (int j = m; j < length; j++) {
        
                    if ((i & (1 << (j - m))) != 0) {
        
                        total += nums[j];
                    }
                }
                if (total == 0 || (rigthSum != total && leftSet.contains(-total))) {
        
                    return true;
                }
            }
            return false;
        }
    }

[Link 1]: https://leetcode.cn/problems/split-array-with-same-average/solution/shu-zu-de-jun-zhi-fen-ge-by-leetcode-sol-f630/