查找两个数组中的对，使得相乘时成为一个完美的平方

一尘不染

查找两个数组中的对，使得相乘时成为一个完美的平方

algorithm

给定两个这样的整数数组：

int [] a = {2，6，10，13，17,18};
int [] b = {3，7，8，9，11，15};

我如何才能从这两个数组中找到对，以便在相乘时它们成为完美的平方？

例如，在上述阵列中，{2,8}＆{18,8}是两对。

现在，我的方法是蛮力，在这里我要遍历两个数组：

int count = 0;
for (int i = 0; i < arr1.Length; i++)
{
    for (int j = 0; j < arr2.Length; j++)
    {
         var x = arr1[i] * arr2[j];
         long s = (long)Math.Sqrt(x);
         if (x == s * s)
               count += 1;                   
     }
}

我如何有效地做到这一点？

阅读 349

2020-07-28

共1个答案

一尘不染

任何两个数字，其中每个素数的个数为偶数，将形成一个有效对。否则，任何具有一个或多个质因子的奇数的数字只能与具有相同奇数的相同因子的另一个数配对。这意味着我们需要存储的每个数字是哪个素数具有奇数。这可以散列。

a = { 2, 6, 10, 13, 17,18 }; 
b = { 3, 7, 8, 9, 11, 15 };

散列较短的数组，其中键是素数和奇数的组合，值是数组中相应的索引列表：

a = {
  2: [0,5],
  2-3: [1], 
  2-5: [2], 
  13: [3],
  17: [4]
}

遍历第二个数组，并精确匹配具有奇数计数的素因数：

b[0] -> 3, no match
b[1] -> 7, no match
b[2] -> 2, match with a[0] and a[5] -> 2 * 8 and 18 * 8 are perfect squares
b[3] -> None, no match
b[4] -> 11, no match
b[5] -> 3-5, no match

2020-07-28