在两个数组中找到对，这样当相乘时变成一个完美的正方形

Question

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

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;                   
     }
}

我怎样才能有效地做到这一点？

Answer 1

我设法使用 LINQ 简化了它：

int[] arr1 = { 2, 6, 10, 13, 17, 18 };
int[] arr2 = { 3, 7, 8, 9, 11, 15 };
int count = arr1.Sum(t => (from t1 in arr2 select t*t1 into x let s = (long) Math.Sqrt(x) where x == s*s select x).Count());

Answer 2

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

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

Answer 3

我会在左画根后检查你是否有小数位。如果没有，那么您就有了完美的平方根：

void Main()
{
    int[] arr1 = { 2, 6, 10, 13, 17, 18 };
    int[] arr2 = { 3, 7, 8, 9, 11, 15 };

    List<string> PairList = new List<string>();

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < arr2.Length; j++)
        {
            if (Math.Sqrt(arr1[i] * arr2[j]) % 1 == 0)
            {
                PairList.Add(String.Format("{0} & {1}", arr1[i] , arr2[j]));
            }           
        }
    }

    PairList.Dump();
}

Answer 4

对于整数大于 0 的有序数组（仅对检测最大值重要），借助改进的埃拉托色尼筛法，我认为复杂度为 O(max * log(max) * log(log( max)) + n) 并且需要额外的 O(max) space （与标准 O(n^2) 和 O(1) 相比，这可能是一个巨大的改进或非常糟糕，具体取决于 n 和 max space 且不依赖于 max):

long total = 0;
int max = (a[a.length - 1] > b[b.length - 1] ? a[a.length - 1] : b[b.length - 1]) + 1;
int[] sieve = new int[max], anti = new int[max], count = new int[max];
for (int i = 1; i < max; i++) {
    sieve[i] = i; // using numbers and divide by prime instead of booleans
    anti[i] = 1; // number by which i has to be multiplied to get the smallest square
}
for (int i = 2; i < max; i++) {
    if (sieve[i] == i) { // i is prime
        for (int j = i; j < max; j += i) {
            boolean odd = false;
            do {
                odd = !odd;
                sieve[j] /= i;
            } while (sieve[j] % i == 0);
            if (odd)
                anti[j] *= i;
        }
    } // if you know the max over all the calls the above has only to be done once
} // except for resetting count and total, so we would get O(n) because max is constant
for (int i = 0; i < a.length; i++)
    count[anti[a[i]]]++; // hash map for count is better than array if n < max
for (int i = 0; i < b.length; i++)
    total += count[anti[b[i]]];

平方数将映射到 1，其他数将映射到因数分解中具有奇数指数的素数的乘积。在您的示例中，每个数字都映射到自身，但 8 => 2、9 => 1、18 => 2 除外。18 以下的其他有趣数字（不是正方形或映射到自身）：12 => 3。迭代 a 时算法在访问 2 时将 2 的计数增加一次，在访问 18 时增加一次。当 b 的迭代访问 8 时，总数将增加 2，这是两个数组之间的唯一匹配项，因此是最终结果。

在两个数组中找到对，这样当相乘时变成一个完美的正方形

Find pairs in two arrays such that when multiplied becomes a perfect square

c#

arrays

algorithm

perfect-square