Leetcode 805. 数组的均值分割

给定你一个整数数组 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^4 
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

• 解法一：折半搜索
  首先，对于average(A) == average(B),我们可以通过数学层面上的分析进行简化。
  $su{m}_A$代表A数组的和，sum代表整个数组的和，j代表A数组数的个数，n代表整个数组数的个数
  $\frac{su{m}_A}{j}=\frac{sum-su{m}_A}{n-j}$ $-->\frac{su{m}_A}{j}=\frac{sum}{n}=avg$
  我们对于nums中每一个数减去一个avg，那么最后整个nums数组的平均值为0，那么我们只要求得一个子集和其平均值为0即可(不能全选)，由于n=30，因此通过全部枚举子集的时间复杂度为$O(2^n)$会导致超时。
  我们可以将整个数组一分为2，对于前部分寻找所有子集和能够凑成的值，若直接就能凑成0，那么直接返回true。利用哈希记录下前部分数组的所有状态和，这里可以使用二进制位来枚举每一个数是否选中。
  再对后半个数组继续执行类似操作，求出所有子集和，判断是否能够前面数相加变成0，若能相加为0则返回true。

• 由于avg可能为浮点数，直接相减后运算会受浮点数的影响，那么可以对于所有的数都乘上一个n
  $\frac{su{m}_A}{j}=\frac{sum}{n}$$-->\frac{su{m}_A\ast n}{j}=\frac{sum\ast n}{n}=sum$
  那么只需要对所有的数再减去一个sum值，那么nums的平均值最后就会变成0,并且这时候不会产生浮点数，因为平均值为sum是一个整数。

• 时间复杂度：$O(n\ast 2^{n/2})$

• 空间复杂度：$O(2^{n/2})$

 class Solution {
    int sum, n, m;
    Map<Integer, Boolean> mp = new HashMap<>();
    public boolean splitArraySameAverage(int[] nums) {
        sum = Arrays.stream(nums).sum();
        n = nums.length;
        m = n / 2;
        if (n == 1) return false;
        for (int i = 0; i < n; i++) nums[i] = nums[i] * n - sum;
        //从前部分数组中求出所有子集和
        for (int i = 1; i < (1 << m); i++) {
            int st = 0, cnt = 0;
            for (int j = 0; j < m; j++) if (((1 << j) & i) != 0) st += nums[j];
            mp.put(st, true);
            if (st == 0) return true;
        }
        //从后部分求解
        sum = (1 << (n - m)) - 1; //判断不能全选
        for (int i = 1; i < (1 << (n - m)); i++) {
            int st = 0, cnt = 0;
            for (int j = 0; j < (n - m); j++) if (((1 << j) & i) != 0) st += nums[j + m];
            if (st == 0 || mp.containsKey(-st) && i != sum) 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

• 解法二：动态规划
  由于$\frac{su{m}_A}{j}=\frac{sum}{n}=avg$，那么其实我们需要寻找一个子集和$su{m}_A$使得$sumA=avg\ast j$
  那么可以将该问题抽象与类型01背包问题。现在给定n个数，找出j个数是否能够
  凑成$su{m}_A=j\ast avg$
  类似于01背包问题的状态集合，从前k个数中选了j个数是否能够组合成i
  状态集合：$dp[i][j]$对于目前已经遍历的数是否能够选出j个数组合成i
  状态计算：对于当前遍历的数x来说，$dp[i][j]|=dp[i-x][j-1]$
  对于avg(A) = avg(B), 可以知道其中子集的个数必然小于等于n/2,因此只需要寻找个数为n/2即可。
• 时间复杂度：$O(n^2\ast sum)$
• 空间复杂度：$O(n\ast sum)$

class Solution { 
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length, sum = Arrays.stream(nums).sum();
        boolean[][] dp = new boolean[sum + 5][n / 2 + 5];
        dp[0][0] = true;
        for (int x: nums) {
            for (int i = sum; i >= x; i--) { //需要倒着计算 类似于01背包滚动数组优化，利用的其实是上一层的结果，从三维降到两维
                for (int j = 1; j <= n / 2; j++) {
                    dp[i][j] |= dp[i - x][j - 1]; 
                }
            }
        }
        for (int j = 1; j <= n / 2; j++) if ((sum * j) % n == 0 && dp[sum * j / n][j]) return true;
        return false;
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 解法三：动态规划 + 位运算
  对于解法二，时间复杂度为$O(n^2\ast sum)$，利用位运算进行优化，我们可以知道某个值i可以有多个可能的j组合成, 那么利用位运算来表示能够当前的i可以有多少种j来表示。
  例如: 0110，代表可以有1个数，2个数组合成i，对于某一位的二进制位若为1,代表可以由几个数组合成，第i位位1，代表可以由i个数组成。
  状态计算：$dp[i]|=dp[i-x]<<1$; 以前状态为$dp[i-x]$，现在新添加一个数x，那么以前的个数情况都要增加1

class Solution { 
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length, sum = Arrays.stream(nums).sum();
        int[] dp = new int[sum + 5];
        dp[0] = 1; //00001代表用0个数
        for (int x: nums) {
            for (int i = sum; i >= x; i--) {
                dp[i] |= dp[i - x] << 1; 
            }
        }
        for (int j = 1; j <= n / 2; j++) if ((sum * j) % n == 0 && ((dp[sum * j / n] & (1 << j)) != 0)) return true;
        return false;
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14