3

我被问到一个工作面试的问题，我不知道正确答案....

问题是：

如果您有一个介于 1 到 100 之间的 10 000 000 个整数的数组，请（有效地）确定有多少对这些整数的总和为 150 或更少。

如果没有循环中的循环，我不知道如何做到这一点，但这不是很有效。

有人请给我一些指示吗？

4

3 回答 3

7

一种方法是创建一个包含 100 个元素的较小数组。循环遍历 10,000,000 个元素并计算每个元素的数量。将计数器存储在 100 个元素的数组中。

    // create an array counter of 101 elements and set every element to 0
    for (int i = 0; i < 10000000; i++) {
          counter[input[i]]++;
    }

然后从 1 到 100 执行第二个循环 j。在其中，有一个从 1 到 min(150-j,j) 的循环 k。如果 k!=j，则添加 counter[j]*counter[k]。如果 k=j，则添加 (counter[j]-1)*counter[j]。

总和就是你的结果。

您的总运行时间以 10,000,000 + 100*100 = 10,010,000 为界（实际上比这更小）。

这比 (10,000,000)^2 快很多，即 100,000,000,000,000。

当然，你必须在内存中放弃 101 个 int 空间。

完成后删除计数器。

还要注意（正如在下面的讨论中所指出的）这是假设顺序很重要。如果顺序无关紧要，只需将结果除以 2。

于 2013-01-10T07:16:35.537 回答
0

first, I would sort the array. Then you start a single pass through the sorted array. You get the single value n in that cell and find the correspondent lowest value that is still allowed (e.g. for 15 it is 135). Now you find the index of this value in the array and that's the amount of pairs for n. Sum up all these and you have (if my mind is working correctly) counted each pair twice, so if you divide the sum by 2, you have the correct number.

The solution should be O(n log n) compared to the trivial one, which is O(n^2)

于 2013-01-10T09:30:00.050 回答
0

这类问题总是需要数学洞察力和高效编程的结合。他们不想要蛮力。

第一洞察力

数字可以根据它们与其他组的配对方式进行分组。

将它们放入：

1 - 50 | 51 - 75 | 76 - 100
  A    |    B    |    C
  • 组A可以与任何东西配对。
  • 组可以与和B配对ABpossibly C
  • 组可以与andC配对，但不能Apossibly BC

这possibly是我们需要更多洞察力的地方。

第二洞察

对于 B 中的每个数字，我们需要检查有多少数字直到其补码 150。例如，对于62from group ，B我们想从 group 中知道C有多少数字小于或等于88。

对于其中的每个数字，C我们将计数相加，例如 76、77、78、...、88 的计数。这在数学上称为部分和。

在标准库中有一个函数可以生成partial_sum

vector<int> tallies(25); // this is room for the tallies from C
vector<int> partial_sums(25);

partial_sum(tallies.begin(), tallies.end(), partial_sums.begin());

对称性意味着这个总和只需要对一组进行。

第三（很久以后）洞察力

计算组的总数，A也B可以使用 来完成partial_sum。因此，与其只计算 groupC并且必须以其他方式跟踪总数，不如存储从 1 到 100 的每个数字的总数，然后在整个事物上创建 partial_sum。partial_sums[50]会给你小于或等于 50 的数字数量，partial_sums[75] 小于或等于 75 的数字，partial_sums[100] 应该是 1000 万，即所有小于或等于 100 的数字。

最后我们可以计算 和 的B组合C。我们想将 50 和 100、51 和 99、52 和 98 等的总数的所有倍数相加。我们可以通过迭代从 50 到 75 的计数以及从 100 到 75 的部分总和来做到这一点。有一个标准inner_product可以处理这个的库函数。

这对我来说似乎很线性。

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 100);

vector<int> tallies(100);
for(int i=0; i < 10000000; ++i) {
    tallies[dis(gen)]++;
}

vector<int> partial_sums(100);
partial_sum(tallies.begin(), tallies.end(), partial_sums.begin());

int A = partial_sums[50];
int AB = partial_sums[75];
int ABC = partial_sums[100]; 
int B = AB - A;
int C = ABC - AB;

int A_match = A * ABC;
int B_match = B * B;
int C_match = inner_product(&tallies[50], &tallies[75],
                            partial_sums.rend(), 0);
于 2013-01-10T10:34:09.563 回答