时间戳

首页 > 解决方案 > Make two array sum same with limited values

java - Make two array sum same with limited values

问题描述

I have two arrays A & B (size of the array is 1 to 100,000) that can take values only 1,2,3,4,5,6.

Now my task is to make minimum numbers to be changed in arrays such that the sum of both the arrays is the same.

Example 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.

Example 3:

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

Method signature looks like this.

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

   // 
}

I am able to get answer for example 3 with simple condition. Bit not for first 2 examples.

What approach should I follow to solve this program? As we can turn each and every element in A & B and do a comparison, but that is more complex.

标签： javaalgorithm

解决方案

算法可以如下：

准备数据部分

遍历数组 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为较大的数组，并且可以轻松计算出您需要更改的数量以及是否足够或者您更改了所有这些和然后你将继续5to1和2to6等。

例子

想象一下A.length500 和300。和B.length的总和。你会发现6 有 30 次重复，1 有 20 次重复。在你将所有这些 6 更改为 1，因此将其减少到 total of并且在你将所有这些 1 更改为 6 并增加值，因此。您总共做了 50 次更改。A=1000B=700ABA30*5=150A=850B20*5=100B=800

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

推荐阅读