java - 用有限的值使两个数组和相同

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;

   // 
}

我能够以简单的条件获得示例 3 的答案。位不是前 2 个例子。

我应该遵循什么方法来解决这个程序？因为我们可以将 A 和 B 中的每个元素都翻转并进行比较，但这更复杂。

Answer 1

算法可以如下:

准备数据部分

遍历数组 A 和 B 中的所有项目，找出每个数组中每个数字 (1,2,3,4,5,6) 的数量。最好有 2d 数组来存储这些数字的索引，以便您以后可以轻松访问它。

即数组 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
在处理过程中，您也可以计算总和，但即使没有它，现在只需通过 2darray 中每个子数组的长度就可以轻松找到总和。

算法

要找到最小的变化量，您将首先找出哪个总和较小，哪个较大。那么最好的改变就是开始改变 1值为 6在较小的数组中或更改 6值为 1在更大的阵列中。然后 2至 6在较小的阵列和 5至 1在更大的阵列中。然后继续其他数字。

在此过程中，您可以根据已有的索引更改数组，并根据需要进行更改以使两个数组达到相同的总和。这是详细的算法，它将向您展示两个阵列实际上如何满足您的需求。它的 O(n) ，所以绝对没有办法让它更快，因为你必须遍历所有字段才能获得 sum .

我建议这样做，以便您可以看到实际结果。另一方面，如果你更深入地思考，它可以更容易地完成，如果你只是寻找正确的答案——你只需要知道每个数组中每个数字的次数，然后找出需要多少次更改只是通过简单的数学。你已经知道了，你只是变了个样 1至 6在较小的数组中，直到所有 6至 1在更大的数组中，可以很容易地计算出您需要更改多少个，如果足够，或者您更改所有这些，然后您将继续 5至 1和 2至 6等等。

示例

想象一下 A.length是 500 和 B.length是 300。 A=1000 的总和和 B=700 .你发现 A有 30 次重复数字 6 和 B有 20 次重复数字 1。在 A您将所有这些 6 更改为 1，因此将其减少 30*5=150总计 A=850并在 B您将所有这些 1 更改为 6 并增加值 20*5=100因此 B=800 .您总共进行了 50 次更改。

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