题目描述

LC2035. 将数组分成两个数组并最小化数组和的差

样例

blablabla

算法1

(折半查找 + 二分)

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size();
        int k = n/2;
        vector<vector<int>> f(k + 1);

        for (int i = 0; i < 1<<k; ++i) {
            int cnt = 0, sum = 0;
            for (int j = 0; j < k; ++j) {
                if ((i >> j) & 1) {
                    cnt++; sum += nums[j];
                } else sum -= nums[j];
            }
            f[cnt].push_back(sum);
        }

        for (auto& vec : f) sort(vec.begin(), vec.end());

        int res = INT_MAX;
        for (int i = 0; i < 1<<k; ++i) {
            int cnt = 0, sum = 0;
            for(int j = 0; j < k; ++j) {
                if ((i >> j) & 1) {
                    cnt++; sum += nums[k + j];
                } else sum -= nums[k + j];
            }

            vector<int>& vec = f[k - cnt];
            int l = 0, r = vec.size() - 1;
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                if (vec[mid] + sum <= 0) l = mid;
                else r = mid - 1;
            }
            res = min(res, abs(vec[r] + sum));
        }
        return res;
    }
};