【动态规划】【数学】【C++算法】805 数组的均值分割

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

数学

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⁴

动态规划

令n=nums.length half=n/2。不失一般性，令A的长度小于等于B，则lena的长度取值范围[1,half]，lenb=n-lena。

数组A的和为：Sumi = 0 : n − 1 \Large_{i=0}^{:n-1}i=0:n−1nums[i]*lena/n ,数组A的和必须是整数。nums[i]的和最大为10⁴*30 ，lean最大为15，可以直接相乘，看对n的余数是否为0。如果超出整数范围，可以先对lena和n约分。

预处理CountToTotal

将nums分成两部分。vLeft[i]记录所有从nums[0,half)选择i个数 可能的和。 vRight[i]记录所有从nums[half,n)中选择i个数的和。下面以vLeft为例，vRightei类似。三层循环

第一层循环：枚举[0,half)。时间复杂度O(n)

第二层循环：从大到小枚举vLeft[j]。 时间复杂度(n)。

第三层循环：枚举vLeft[j-1]。 时间复杂度O(2^n)

动态规划的转移方程：本轮的vLeft[j]一定是上一轮的vLeft[j-1]+nums[i]。总时间复杂度O(15152¹⁵) 约10⁶

处理

第一层循环：用变量i枚举lena。

第二层循环：枚举A从左边选择了j个元素，j的取值范围[0,i]。

第三层循环：通过iLeft枚举vLeft[j]，看vRight[i-j]是否存在totalA - iLeft。

时间复杂度: O(nn2ⁿ)

代码

核心代码

int GCD(int n1, int n2)
{
  int t1 = min(n1, n2);
  int t2 = max(n1, n2);
  if (0 == t1)
  {
    return t2;
  }
  return GCD(t2 % t1, t1);
}
class Solution {
public:
  bool splitArraySameAverage(vector<int>& nums) {
    const int n = nums.size();
    const int half = n / 2;
    vector<unordered_set<int>> vLeft(1), vRight(1);   
    CountToTotal( vLeft, nums.data(),0, half);
    CountToTotal(vRight, nums.data()+half, 0, n-half);
    const int total = std::accumulate(nums.begin(), nums.end(),0);
    for (int i = 1; i <= half; i++)
    {
      const int iGCD = GCD(i, n);
      if (0 != total % (n / iGCD))
      {
        continue;//A的和必定为整数
      }
      const int totalA = total * i / n;
      for (int j = 0; j <= i; j++)
      {// A数组总共选择i个，其中从左边选择j个
        for (const auto& iLeft : vLeft[j])
        {
          if (vRight[i - j].count(totalA - iLeft))
          {
            return true;
          }
        }
      }
    }
    return false;
  }
  void CountToTotal(std::vector<std::unordered_set<int>>& v, const int* p,int left,int r)
  {
    v[0].emplace(0);
    for (int i = left; i < r ; i++)
    {
      v.emplace_back();
      for (int j = v.size() - 1; j >= 1; j--)
      {
        for (const auto& pre : v[j - 1])
        {
          v[j].emplace(pre + p[i]);
        }
      }
    }
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums;
  {
    Solution sln;
    nums = { 1,2,3,4,5,6,7,8 };
    auto res = sln.splitArraySameAverage(nums);
    Assert(true, res);
  }
  {
    Solution sln;
    nums = { 3,1};
    auto res = sln.splitArraySameAverage(nums);
    Assert(false, res);
  }
  {
    Solution sln;
    nums = { 18,10,5,3 };
    auto res = sln.splitArraySameAverage(nums);
    Assert(false, res);
  }
  
}

2023年1月

class Solution {

public:

bool splitArraySameAverage(vector& nums) {

if (1 == nums.size())

{

return false;

}

const int iLeftMaxLen = nums.size() / 2;

const int iRightMaxLen = nums.size() - iLeftMaxLen;

vector<std::unordered_set> vLeftLenSums(iLeftMaxLen+1),vRightLenSums(iRightMaxLen+1);

vLeftLenSums[0].insert(0);

for (int i = 0; i < iLeftMaxLen; i++)

{

for (int j = i ; j >=0 ; j-- )

{

for (auto& it : vLeftLenSums[j])

{

vLeftLenSums[j + 1].insert(it +nums[i]);

}

}

vLeftLenSums[1].insert(nums[i]);

}

vRightLenSums[0].insert(0);

for (int i = iLeftMaxLen; i < nums.size(); i++)

{

for (int j = i - iLeftMaxLen; j >= 0; j–)

{

for (auto& it : vRightLenSums[j])

{

vRightLenSums[j + 1].insert(it + nums[i]);

}

}

}

int iTotalSum = std::accumulate(nums.begin(), nums.end(), 0);

for (int iALen = 1; iALen + 1 <= nums.size(); iALen++)

{

double dSum = iTotalSum 1.0 / nums.size() iALen;

int iSum = dSum;

bool bInt = ((dSum - iSum) < 0.0001) || ((dSum - iSum) > 0.9999);

if (!bInt)

{

continue;

}

for (int iLeftLen = max(0,iALen-iRightMaxLen); (iLeftLen <= min(iALen, iLeftMaxLen)); iLeftLen++)

{

for (const auto& it : vLeftLenSums[iLeftLen])

{

if (vRightLenSums[iALen - iLeftLen].count(iSum - it))

{

return true;

}

}

}

}

return false;

}

};