2

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

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

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

4

4 回答 4

7

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

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

遍历第二个数组并完全匹配prime-factor-with-odd-count-combination：

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
于 2017-05-19T15:03:12.827 回答
1

对于在 Eratosthenes 的改进筛的帮助下整数 > 0 的有序（仅对检测最大值很重要）数组，我认为复杂度是 O(max * log(max) * log(log(max)) + n ) 并且需要 O(max) 额外空间（与具有 O(1) 空间且不依赖于 max 的标准 O(n^2) 相比，取决于 n 和 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，这是两个数组之间的唯一匹配，因此是最终结果。

于 2017-05-19T17:37:36.047 回答
0

我设法使用 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());
于 2017-05-19T14:57:08.693 回答
0

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

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();
}
于 2017-05-19T15:05:04.393 回答