Question

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

English Version

题目描述

给你一个长度为 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

解法

方法一

class Solution:
  def minimumDifference(self, nums: List[int]) -> int:
    n = len(nums) >> 1
    f = defaultdict(set)
    g = defaultdict(set)
    for i in range(1 << n):
      s = cnt = 0
      s1 = cnt1 = 0
      for j in range(n):
        if (i & (1 << j)) != 0:
          s += nums[j]
          cnt += 1
          s1 += nums[n + j]
          cnt1 += 1
        else:
          s -= nums[j]
          s1 -= nums[n + j]
      f[cnt].add(s)
      g[cnt1].add(s1)

    ans = inf
    for i in range(n + 1):
      fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))
      # min(abs(f[i] + g[n - i]))
      for a in fi:
        left, right = 0, len(gi) - 1
        b = -a
        while left < right:
          mid = (left + right) >> 1
          if gi[mid] >= b:
            right = mid
          else:
            left = mid + 1
        ans = min(ans, abs(a + gi[left]))
        if left > 0:
          ans = min(ans, abs(a + gi[left - 1]))
    return ans

class Solution {
  public int minimumDifference(int[] nums) {
    int n = nums.length >> 1;
    Map<Integer, Set<Integer>> f = new HashMap<>();
    Map<Integer, Set<Integer>> g = new HashMap<>();
    for (int i = 0; i < (1 << n); ++i) {
      int s = 0, cnt = 0;
      int s1 = 0, cnt1 = 0;
      for (int j = 0; j < n; ++j) {
        if ((i & (1 << j)) != 0) {
          s += nums[j];
          ++cnt;
          s1 += nums[n + j];
          ++cnt1;
        } else {
          s -= nums[j];
          s1 -= nums[n + j];
        }
      }
      f.computeIfAbsent(cnt, k -> new HashSet<>()).add(s);
      g.computeIfAbsent(cnt1, k -> new HashSet<>()).add(s1);
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i <= n; ++i) {
      List<Integer> fi = new ArrayList<>(f.get(i));
      List<Integer> gi = new ArrayList<>(g.get(n - i));
      Collections.sort(fi);
      Collections.sort(gi);
      for (int a : fi) {
        int left = 0, right = gi.size() - 1;
        int b = -a;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (gi.get(mid) >= b) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        ans = Math.min(ans, Math.abs(a + gi.get(left)));
        if (left > 0) {
          ans = Math.min(ans, Math.abs(a + gi.get(left - 1)));
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int minimumDifference(vector<int>& nums) {
    int n = nums.size() >> 1;
    vector<vector<int>> f(n + 1), g(n + 1);
    for (int i = 0; i < (1 << n); ++i) {
      int s = 0, cnt = 0;
      int s1 = 0, cnt1 = 0;
      for (int j = 0; j < n; ++j) {
        if (i & (1 << j)) {
          s += nums[j];
          ++cnt;
          s1 += nums[n + j];
          ++cnt1;
        } else {
          s -= nums[j];
          s1 -= nums[n + j];
        }
      }
      f[cnt].push_back(s);
      g[cnt1].push_back(s1);
    }
    for (int i = 0; i <= n; ++i) {
      sort(f[i].begin(), f[i].end());
      sort(g[i].begin(), g[i].end());
    }
    int ans = INT_MAX;
    for (int i = 0; i <= n; ++i) {
      for (int a : f[i]) {
        int left = 0, right = g[n - i].size() - 1;
        int b = -a;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (g[n - i][mid] >= b)
            right = mid;
          else
            left = mid + 1;
        }
        ans = min(ans, abs(a + g[n - i][left]));
        if (left > 0) ans = min(ans, abs(a + g[n - i][left - 1]));
      }
    }
    return ans;
  }
};

func minimumDifference(nums []int) int {
  n := len(nums) >> 1
  f := make([][]int, n+1)
  g := make([][]int, n+1)
  for i := 0; i < (1 << n); i++ {
    s, cnt := 0, 0
    s1, cnt1 := 0, 0
    for j := 0; j < n; j++ {
      if (i & (1 << j)) != 0 {
        s += nums[j]
        cnt++
        s1 += nums[n+j]
        cnt1++
      } else {
        s -= nums[j]
        s1 -= nums[n+j]
      }
    }
    f[cnt] = append(f[cnt], s)
    g[cnt1] = append(g[cnt1], s1)
  }

  for i := 0; i <= n; i++ {
    sort.Ints(f[i])
    sort.Ints(g[i])
  }
  ans := 1 << 30
  for i := 0; i <= n; i++ {
    for _, a := range f[i] {
      left, right := 0, len(g[n-i])-1
      b := -a
      for left < right {
        mid := (left + right) >> 1
        if g[n-i][mid] >= b {
          right = mid
        } else {
          left = mid + 1
        }
      }
      ans = min(ans, abs(a+g[n-i][left]))
      if left > 0 {
        ans = min(ans, abs(a+g[n-i][left-1]))
      }
    }
  }
  return ans
}

func abs(x int) int {
  if x > 0 {
    return x
  }
  return -x
}