使用有限的值使两个数组的总和相等

Question

我有两个数组A & B（数组的大小为1到100,000），它们只能取值1、2、3、4、5、6。

现在我的任务是尽可能少地更改数组中的数字，使得两个数组之和相等。

例子2：

A=[5,4,1,2,6,6] & B=[2], we have to make A as [1,1,1,1,1,1] so we have to change A 5 times and then B=[6] once, so function should return 6.

示例3：

A=[1,2,3,4,3,2,1] and B[6], function should return -1.

方法签名看起来像这样。

public int task(int[] A, int[] B) {
   int diff = Math.abs(A.length - B.length);
   if(diff >=6) return -1;

   // 
}

我能用简单条件得到第三个示例的答案，但前两个示例不行。

解决这个问题应该采取什么方法？虽然我们可以将A和B中的每个元素都转换并进行比较，但那样会更加复杂。

- learner

---

纯粹的代码撰写请求在 Stack Overflow 是不受欢迎的——我们期望这里的问题与特定的编程问题有关，但我们很乐意帮助你自己编写它！告诉我们 你已经尝试过什么，以及你遇到了哪些困难。这也将有助于我们更好地回答你的问题。 - chriptus13

@chriptus13，同意你的观点，但是在过去的几天里，我一直在尝试理解从哪里开始，但是却陷入了如何处理这个任务的困境。因此，我需要一些帮助。 - learner

你的第三个例子的条件是错误的：例如，长度为5的数组，所有元素都是6，其总和与长度为30的数组，所有元素都是1，其总和相同（尽管长度差异远大于6）。 - Costi Ciudatu

Answer 1

算法可以按照以下步骤进行：

数据准备部分

遍历数组A和B中的所有项，找出每个数字（1,2,3,4,5,6）在每个数组中出现的次数。最好使用二维数组存储这些数字的索引，以便稍后可以轻松访问。

例如，数组A=[1,1,1,4,6,4]将被转换为新的二维数组，如下所示：

2darr=
[]
[0,1,2]
[]
[]
[3,5]
[]
[4]

所以，例如当您想查看有多少个 1 时，您可以查看 2darr[1].length ，结果为 3。而当您想找出它在哪里时，2darr[1][0] 将为您获取源数组中的索引，而 A[0] 确实是 1

在处理过程中，您还可以计算总和，但即使没有它，现在也可以很容易地通过遍历二维数组中每个子数组的长度来找到总和。

算法

要找到最小更改量，您首先需要找出哪个和较小，哪个和较大。然后最佳更改是开始在较小的数组中将 1 值更改为 6 或在较大的数组中将 6 值更改为 1。然后，在较小的数组中将 2 更改为 6，在较大的数组中将 5 更改为 1。然后继续处理其他数字。

在处理过程中，可以基于已经拥有的索引更改数组，并一直这样做，直到将两个数组的和相同为止。这是详细的算法，将向您展示实际上两个数组看起来如何以满足您的需求。它的 O(n)，因此绝对没有办法使其更快，因为您必须遍历所有字段才能获取 sum。

我建议您这样做，以便您可以看到实际结果。另一方面，如果您深入思考，可以更轻松地完成它，只需寻找正确的答案-您只需要知道每个数组中每个数字出现的次数，然后通过简单的数学计算找出需要更改多少次。您已经知道，您只需在较小的数组中更改最多所有的 1 为 6 ，在较大的数组中更改最多所有的 6 为 1，并且可以轻松地计算出需要更改多少个，并确定是否足够或者你会更改所有的 1 至 6 然后继续处理 5 至 1 和 2 至 6 等等。

例子

假设 A.length 是 500，B.length 是 300。 A = 1000，B = 700。你发现 A 中数字 6 重复了 30 次，而 B 中数字 1 重复了 20 次。你将 A 中的所有数字 6 更改为 1，因此将其减少了 30*5=150，总数变为 A=850，然后在 B 中将所有数字 1 改为 6 并增加了值 20*5=100，因此 B=800。你总共做了 50 次更改。

然后你继续用小数组中较大的数字和大数组中较小的数字。你发现 A 中有 100 个数字 5。每次将 5 减少到 1 会使值减少 4。现在只差 50 的值差异。 50/4=12.5，因此你需要更改 13 个数字，然后就完成了。答案是最小更改量为 63。

- libik

Answer 2

不可能性标准很简单，正如你所猜测的那样，但它与你想象的不同：它取决于数组的长度，这确定了它们的最小和最大值。较短的数组不能产生比其长度的6倍更大的总和（所有元素都是6），而较长的数组不能产生比其长度更小的总和（所有元素都是1）：

if( Math.min(A.length, B.length) * 6 < Math.max(A.length ,B.length) )
  return -1;

然后，您需要像其他答案所描述的那样进行求和和统计，但也许有一个稍微不同的解释。为了使这两个总和相遇，可以增加较小的总和并减少较大的总和。为了尽可能少的步骤，您始终希望采取最大的步骤，通过开始在较小的总和中用6替换1（每次替换将总和增加5），在较大的总和中用1替换6（每次替换将总和减少5），等等。

由于您不想生成步骤（至少我是这样理解的），因此实际上只需跟踪差异并计算成对出现的数量（较大总和数组中的6和较小总和数组中的1，然后再使用5-2等）。实际上，甚至可以在开始时进行这种配对，而不知道哪个是更大/更小的总和，因为这些配对将保持不变，只是它们的方向发生了改变。

示例是JavaScript，因此它可以在此处运行，但我尽量以Java编写它：

function task(A,B){
  if( Math.min(A.length, B.length) * 6 < Math.max(A.length, B.length) )
    return -1;
    
  var diff=0;
  var statistics=[0,0,0,0,0,0]; // would be a new int[6] in Java
  for(var item of A){ // for(int item : A) in Java
    // this loop guesses that A has the larger sum
    diff+=item;
    statistics[item-1]++; // 1s are counted in [0], 2s in [1], ... 6s in [5]
  }
  for(var item of B){ // for(int item : B) in Java
    // this loop guesses that B has the smaller sum
    diff-=item;
    statistics[6-item]++; // 1s are counted in [5], 2s in [4], ... 6s in [0]
  }
  if(diff<0){
    // the guess was wrong, swaps are needed
    diff=-diff;
    for(var i=0;i<3;i++){
      var swap=statistics[i];
      statistics[i]=statistics[5-i];
      statistics[5-i]=swap;
    }
  }
  
  var log=[A.join()," ",B.join()," ",diff," ",statistics.join()].join(); // <-- this one...
  
  // at this point
  // - array indices are conveniently denoting step sizes
  // - diff is non-negative
  // - and we know there is a solution (so we won't run out of array indices for example)
  var changes=0;
  var i=5;
  while(diff>0){
    var step = Math.min(statistics[i], Math.ceil(diff/i));
    // would better be "int step = Math.min(statistics[i], (diff+i-1)/i);" in Java
    // as Math.ceil() produces a double
    changes += step;
    diff -= i*step;
    i--;
  }
  return [changes," ",log].join();                                       // <-- ... and this
                                                                         // are only visuals
  return changes;
}

console.log(task([1,2,3,4,3,2,1],[6]));
console.log(task([6],[1,2,3,4,3,2,1]));
console.log(task([2,3,1,1,2],[5,4,6]));
console.log(task([5,4,6],[2,3,1,1,2]));
console.log(task([5,4,1,2,6,6],[2]));
console.log(task([2],[5,4,1,2,6,6]));

最后我也用Java把它简单地实现了一下：https://ideone.com/mP3Sel

- tevemadar

Answer 3

正如其他人所指出的，我们可以通过贪心算法来解决这个问题。首先计算每个数组中数字的频率，然后从外向内迭代。对于总和较大的数组，迭代负数乘数；对于总和较小的数组，迭代正数乘数。每次选择绝对值最大的乘数，然后选择可用的（并且需要的）最大频率，一旦总和差等于或者反转符号，就停止。

2 3 1 1 2 = 9
mult 5  4  3  2  1  0
freq 2  2  1  0  0  0
     ^ -->

5 4 6 = 15
mult 0 -1 -2 -3 -4 -5
freq 0  0  0  1  1  1
                <-- ^

function f(A, B){
  let freqSm = [0, 0, 0, 0, 0, 0];
  let freqLg = [0, 0, 0, 0, 0, 0];
  let smSum = 0;
  let lgSum = 0;
  let sm = 'A';
  let lg = 'B';
  
  A.map(x => {
    freqSm[x-1]++;
    smSum += x;
  });
  
  B.map(x => {
    freqLg[x-1]++;
    lgSum += x;
  });
  
  if (lgSum < smSum){
    sm = 'B';
    lg = 'A';
    let [_freq, _sum] = [freqSm, smSum];
    freqSm = freqLg;
    freqLg = _freq;
    smSum = lgSum;
    lgSum = _sum; 
  }
  
  const smMult = [5, 4, 3, 2, 1, 0];
  const lgMult = [0,-1,-2,-3,-4,-5];
  const changes = [];
  let diff = lgSum - smSum;
  
  function numTxt(count, num){
    const ws = [, 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
    const countTxt = count < 10 ? ws[count] : count;
    return `${ countTxt } ${ num }${ count > 1 ? 's' : '' }`;
  }
  
  function incSm(i){
    const rem = diff % smMult[i];
    const mult = Math.min(freqSm[i], Math.ceil(diff / smMult[i]));
    diff -= mult * smMult[i];
    let txt;
    if (diff < 0 && rem){
      if (mult > 1)
        txt = `Change ${ numTxt(mult-1, i+1) } to 6 and one to ${ i + 1 + rem } in ${ sm }.`;
      else
        txt = `Change one ${ i + 1 } to ${ i + 1 + rem } in ${ sm }.`;
        
    } else {
      txt = `Change ${ numTxt(mult, i+1) } to 6 in ${ sm }.`;
    }
    changes.push(txt);
  }
  
  function decLg(j){
    const rem = diff % -lgMult[j];
    const mult = Math.min(freqLg[j], Math.ceil(-diff / lgMult[j]));
    diff += mult * lgMult[j];
    let txt;
    if (diff < 0 && rem){
      if (mult > 1)
        txt = `Change ${ numTxt(mult-1, j+1) } to 1 and one to ${ j + 1 - rem } in ${ lg }.`;
      else
        txt = `Change one ${ j + 1 } to ${ j + 1 - rem } in ${ lg }.`;
        
    } else {
      txt = `Change ${ numTxt(mult, j+1) } to 1 in ${ lg }.`;
    }
    changes.push(txt);
  }
  
  for (let i=0; i<6; i++){
    const j = 5 - i;
 
    if (freqSm[i] >= freqLg[j]){
      if (freqSm[i]){
        incSm(i);
        if (diff <= 0)
          return changes.join('\n');
      }
      
      if (freqLg[j]){
        decLg(j);
        if (diff <= 0)
          return changes.join('\n');
      }
      
    } else {
      if (freqLg[j]){
        decLg(j);
        if (diff <= 0)
          return changes.join('\n');
      }
      
      if (freqSm[i]){
        incSm(i);
        if (diff <= 0)
          return changes.join('\n');
      }
    }
  }
  
  return -1;
}

var input = [
  [[2,3,1,1,2], [5,4,6]],
  [[5,4,1,2,6,6], [2]],
  [[1,2,3,4,3,2,1], [6]]
];

for (let [A, B] of input){
  console.log(`A: ${ A }`);
  console.log(`B: ${ B }`);
  console.log(f(A, B));
  console.log('');
}

- גלעד ברקן