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

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] <= 10⁴

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

2.思路

（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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57