5

给定 k 的值。这样 k<=100000 我们必须打印对的数量，使得每对的元素总和可以被 k 整除。在以下条件下，第一个元素应小于第二个元素，并且两个元素都应小于 10 9。

4

4 回答 4

3

我找到了一个解决方案，让a和b数字这样(a+b)%k=0我们必须找到对(a,b)，在哪里a<b，所以让我们计算有多少对(a,b)满足条件a+b=k，例如，如果k=3 0+3=3, 1+2=3, 2+1=3, 3+0=3有 4 对但只有 2 对(K+1)/2 (integer division)与 find 非常相似(a,b)总和为的对2k, 3k,.. nk，解决方案将为，并且与时间复杂度(k+1)/2 + (2k+1)/2 + (3k+1)/2 + ... + (nk+1)/2相等，请注意 if 的情况，因为不能超过给定的约束。(k*n*(n+1)/2 + n)/2O(1)n*k=2*10^9a10^9

于 2013-09-16T22:08:24.890 回答
0

一些伪代码可以帮助您入门。它使用你说你尝试过的蛮力技术，但也许你的代码有问题？

max = 1000000000
numberPairs = 0
for i = 1 to max - 2 do
    for j = i + 1 to max - 1 do
        if (i + j) mod k = 0 then
            numberPairs = numberPairs + 1
        end if
    end do
end do
于 2013-09-12T16:32:10.457 回答
0

一种方法是蛮力：

int numPairs = 0;
for (i = 0; i < 10e9; i++)
{
    for (j = i+1; j < 10e9; j++)
    {
        int sum = i + j;
        if (sum % k == 0) numPairs++;
    }
 }
 return numPairs;

我会留给你来优化它的性能。我至少可以想到一种方法来显着加快速度。

于 2013-09-12T16:32:36.153 回答
0

使用哈希映射解决 O(N) 时间和 O(N) 空间。

概念如下：

If (a+b)%k=0 where

a=k*SOME_CONSTANT_1+REMAINDER_1 

b=k*SOME_CONSTANT_2+REMAINDER_2

then (REMAINDER_1 +REMAINDER_2 )%k will surely be 0

所以对于一个数组 (4,2,3,31,14,16,8) 和 k =5 如果你有一些像下面这样的信息，你可以找出所有的对总和 %k =0

在此处输入图像描述

请注意，最底部的行包含从 0 到 k-1 的所有余数以及与之对应的所有数字。现在您需要做的就是将两个指针移向对方，直到它们相遇。如果两个指针位置都有与之关联的数字，则它们的 sum%k 将为 0

为了解决这个问题，您可以使用哈希表跟踪到目前为止您看到的所有剩余部分

  1. 创建一个哈希映射 Map<Integer, List>。
  2. 用 0 到 k-1 预填充它的键；
  3. 遍历数组并将每个数字的余数放入 Map 中 Key = 余数并将实际数字放入列表中，
  4. 使用相互移动的两个指针迭代键集。和sum += listSizeAsPointedByPointer1 * listSizeAsPointedByPointer2
于 2020-09-26T05:08:54.620 回答