二分查找：LeetCode2035：将数组分成两个数组并最小化数组和的差-阿里云开发者社区

二分查找：LeetCode2035：将数组分成两个数组并最小化数组和的差

2024-01-22 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二分查找：LeetCode2035：将数组分成两个数组并最小化数组和的差

题目

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并最小化两个数组和之差的绝对值。nums 中每个元素都需要放入两个数组之一。

请你返回最小的数组和之差。

示例 1：

输入：nums = [3,9,7,3]

输出：2

解释：最优分组方案是分成 [3,9] 和 [7,3] 。

数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：

输入：nums = [-36,36]

输出：72

解释：最优分组方案是分成 [-36] 和 [36] 。

数组和之差的绝对值为 abs((-36) - (36)) = 72 。

示例 3：

输入：nums = [2,-1,0,4,-2,-9]

输出：0

解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。

数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

参数范围：

1 <= n <= 15

nums.length == 2 * n

-107 <= nums[i] <= 107

折半查找后二分

时间复杂度

O(2ⁿlog2ⁿ)。

变量解释


vLeft	vLeft[i]表示从前n个数据中选择i个数的和，记录所有可能
vRight	类似，记录的是右边

分析

如果从左边选择i个数，那么需要从右边选择n-i个数。假定从左边i个数的和是n1，右边选择n-i个数的和为n2。枚举n1，从v2中选择第一个大于等于n2的数和第一个小于n2的数。iTotal 是nums的和。

n1+n2= iTotal-n1-n2 => n2 =iTotal/2 - n1

iTotal要分奇数和偶数分别处理。我们将所有数都乘以2,iTotal就必定是偶数了。

注意

不要忘记

v[0].emplace_back(0);

代码

核心代码

class Solution {
public:
  int minimumDifference(vector<int>& nums) {
    const int iTotal = std::accumulate(nums.begin(), nums.end(), 0);
    int n = nums.size() / 2;
    vector<vector<int>> vLeft(n + 1), vRight(n + 1);
    auto Build = [&n](vector<vector<int>>& v,int* p, int len)
    {
      v[0].emplace_back(0);
      for (int i = 0; i < len; i++)
      {
        for (int j = n; j >= 1 ; j--)
        {
          for (const auto& num : v[j - 1])
          {
            v[j].emplace_back(num + p[i] * 2);
          }
        }
      }
    };
    Build(vLeft, nums.data(), n);
    Build(vRight, nums.data()+n, n);
    int iRet = INT_MAX;
    for (int i = 0; i <= n; i++)
    {
      auto& v1 = vLeft[i];
      auto& v2 = vRight[n - i];
      sort(v1.begin(), v1.end());
      sort(v2.begin(), v2.end());
      for (const auto& n1 : v1)
      {
        auto it = std::upper_bound(v2.begin(), v2.end(),iTotal- n1);
        if (v2.end() != it)
        {
          iRet = min(iRet, *it + n1 - iTotal);
        }
        if (v2.begin() != it)
        {
          iRet = min(iRet, iTotal - n1 - *(std::prev(it)));
        }
      }
    }
    return iRet;
  }
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector nums;
int res;
{
nums = { 3,9,7,3 };
Solution slu;
auto res = slu.minimumDifference(nums);
Assert(2, res);
}
{
nums = { -36,36 };
Solution slu;
auto res = slu.minimumDifference(nums);
Assert(72, res);
}
{
nums = { 2,-1,0,4,-2,-9 };
Solution slu;
auto res = slu.minimumDifference(nums);
Assert(0, res);
}

//CConsole::Out(res);

}

2023年2月旧版

class Solution {
public:
int minimumDifference(vector& nums) {
m_c = nums.size() / 2;
vectorunordered_set> vSetSumsLeft, vSetSumsRight;
std::vector v1( nums.begin(), nums.begin() + m_c);
CalSumSet(vSetSumsLeft, v1);
std::vector v2(nums.begin() + m_c, nums.end());
CalSumSet(vSetSumsRight,v2 );
int iTotal = std::accumulate(nums.begin(), nums.end(), 0);
int iMin = INT_MAX;
for (int i = 0; i <= m_c; i++ )
{
std::vector v1(vSetSumsLeft[i].begin(), vSetSumsLeft[i].end());
std::vector v2(vSetSumsRight[m_c - i].begin(), vSetSumsRight[m_c - i].end());
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
auto it = v1.begin();
auto ij = v2.rbegin();
while ((it != v1.end()) && (ij != v2.rend()))
{
int iDiff = iTotal - (*it + *ij) * 2;
iMin = min(iMin, abs(iDiff));
if (iDiff > 0)
{
it++;
}
else
{
ij++;
}
}
}
return iMin;
}
static void CalSumSet(vector& vSetSums,vector& nums)
{
int c = nums.size() ;
vSetSums.resize(c + 1);
vSetSums[0].insert(0);
for (const auto& n : nums)
{
vector dp = vSetSums;
for (int i = 0; i < c; i++)
{
for (auto it : vSetSums[i])
{
dp[i + 1].insert(it + n);
}
}
vSetSums.swap(dp);
}
}