C对大型阵列执行计算

发布时间：2020-12-16 09:41:41 所属栏目：百科来源：网络整理

导读：我被问到一个求职面试的问题,我不知道正确答案…. 问题是：如果您有一个介于1和100之间的10 000 000英寸的数组,则(有效地)确定这些总数中有多少对总计为150或更少. 如果没有循环内的循环,我不知道如何做到这一点,但这不是很有效. 有没有人请给我一些指示？

我被问到一个求职面试的问题,我不知道正确答案….

问题是：

如果您有一个介于1和100之间的10 000 000英寸的数组,则(有效地)确定这些总数中有多少对总计为150或更少.

如果没有循环内的循环,我不知道如何做到这一点,但这不是很有效.

有没有人请给我一些指示？

一种方法是创建一个包含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,其中循环k从1到min(150-j,j).如果k！= j,则加上counter [j] * counter [k].如果k = j,则加(计数器[j] -1)*计数器[j].

总和是你的结果.

您的总运行时间最多为10,000 100 * 100 = 10,010,000(实际上小于此值).

这比(10,000)^ 2快得多,即100,000.

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

完成后删除计数器.

还要注意(如下面的讨论中所指出的)这是假设订单很重要.如果顺序无关紧要,只需将结果除以2即可.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!